Треугольник Паскаля

Как устроен треугольник

Треугольник Паскаля начинается с нулевой строки, состоящей из одной единицы. На краях каждой следующей строки стоят единицы, а каждый внутренний элемент равен сумме двух соседей над ним. Строка с номером $n$ содержит $n+1$ чисел: $\binom n0,\binom n1,\ldots,\binom nn$. Нумерация с нуля принципиальна: строка «1, 2, 1» имеет номер 2.

Первые строки выглядят так: 1; затем 1, 1; затем 1, 2, 1; затем 1, 3, 3, 1; затем 1, 4, 6, 4, 1. Это не просто узор. Каждый элемент считает подмножества фиксированного размера, а сложение соответствует разделению выбора на случаи «данный элемент включён» и «не включён».

Как читать строку

Симметрия относительно середины следует из выбора дополнения. Сумма строки $n$ равна $2^n$. При $n$ бросках симметричной монеты числа строки показывают, сколько последовательностей содержат 0, 1, …, $n$ орлов. Для вероятностей эти числа нужно разделить на $2^n$; при несимметричной монете требуется другой вес каждой группы.

Три примера

1. Из строки 1, 4, 6, 4, 1 строим следующую: края 1, внутри $1+4=5$, $4+6=10$, $6+4=10$, $4+1=5$. Получаем 1, 5, 10, 10, 5, 1.
2. Третий элемент строки 5 при счёте позиций с единицы — $\binom52=10$. Он считает выбор двух элементов из пяти, а не трёх.
3. При четырёх независимых бросках честной монеты ровно два орла дают 6 из 16 последовательностей. Вероятность $6/16=3/8$.

Проверки и ограничения

Сумма новой строки должна быть вдвое больше предыдущей. Это удобная проверка арифметики, но не доказательство правильности каждого элемента. Не путайте номер строки и её длину. Треугольник особенно нагляден при небольших $n$; для больших чисел эффективнее сокращать произведения или использовать вычислитель.