Треугольник Паскаля и биномиальные коэффициенты

Треугольник, где каждое число — сумма двух над ним, хранит ответы на тысячи задач о выборе.

Биномиальный коэффициент $\binom{n}{k}$ — число способов выбрать $k$ элементов из $n$ без учёта порядка.

Сколькими способами из 5 человек выбрать команду из 2? Из колоды в 36 карт взять 6? Эти вопросы решает один объект — биномиальный коэффициент, который удобнее всего рассматривать через треугольник Паскаля.

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

На вершине стоит единица. Каждая строка начинается и заканчивается единицей, а внутреннее число равно сумме двух чисел над ним. Это правило выражает основное тождество:

$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$$

Сам коэффициент считается по формуле через факториалы:

$$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}.$$

Числа в $n$-й строке — это коэффициенты разложения $(a+b)^n$, отсюда название «биномиальные».

Строим треугольник

from math import comb

print("Треугольник Паскаля:")
for n in range(6):
    row = [comb(n, k) for k in range(n + 1)]
    print(row)

# Сколько способов выбрать 2 из 5?
print("C(5,2) =", comb(5, 2))
# Сумма строки = степень двойки
print("Сумма строки n=5:", sum(comb(5, k) for k in range(6)))

Вывод:

Треугольник Паскаля:
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
C(5,2) = 10
Сумма строки n=5: 32

Как работает под капотом

Почему сумма $n$-й строки равна $2^n$ (для $n=5$ это 32)? Потому что $\sum_k \binom{n}{k} = (1+1)^n = 2^n$ — это число всех подмножеств из $n$ элементов. Тождество сложения соседей объясняется так: выбирая $k$ элементов из $n$, мы либо берём последний элемент (тогда из остальных нужно выбрать $k-1$), либо не берём (выбираем все $k$ из остальных $n-1$). Сумма этих двух случаев и даёт правило треугольника. В треугольнике спрятаны и числа Фибоначчи (суммы по диагоналям), и узор Серпинского (чётность), и многое другое.

Частые ошибки

Не путайте сочетания $\binom{n}{k}$ (без порядка) с размещениями (с порядком): команда «Аня и Боря» — та же, что «Боря и Аня». Помните, что $\binom{n}{0} = \binom{n}{n} = 1$ (один способ выбрать ничего или всё). И не считайте $\binom{n}{k}$ при $k \gt n$ — там ноль способов.

Итог

$\binom{n}{k}$ — число способов выбрать $k$ из $n$ без порядка.
Правило треугольника: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$.
Формула: $\binom{n}{k} = \dfrac{n!}{k!(n-k)!}$.
Сумма строки равна $2^n$ — числу всех подмножеств.