Биномиальные коэффициенты

Что означает коэффициент

Биномиальный коэффициент $\binom nk$ — число способов выбрать $k$ различных элементов из $n$, не учитывая порядок. Здесь $n$ — неотрицательное целое, $0\le k\le n$. Название связано с раскрытием степени суммы двух слагаемых, но комбинаторное определение полезно само по себе.

Для $k=0$ коэффициент равен единице: пустое подмножество только одно. Для $k=n$ он тоже равен единице. Равенство $\binom nk=\binom n{n-k}$ отражает выбор дополнения: выбрать команду из трёх человек среди десяти — всё равно что указать семерых, которые не вошли.

Два полезных свойства

Разделим $k$-элементные подмножества по тому, входит ли в них последний элемент. Если не входит, остаётся $\binom{n-1}k$ вариантов; если входит — $\binom{n-1}{k-1}$. Так получается рекурсия Паскаля. А сумма всех коэффициентов строки равна $2^n$: каждый из $n$ элементов независимо либо включён в подмножество, либо нет. Это утверждение о числе вариантов, не о вероятностной независимости случайных событий.

Три примера

1. $\binom84=\frac{8\cdot7\cdot6\cdot5}{4\cdot3\cdot2\cdot1}=70$. Сокращение факториалов избавляет от громоздких промежуточных чисел.
2. $\binom{12}{10}=\binom{12}2=66$. Выбрать десять удобно через исключение двух.
3. У множества из пяти элементов всего $2^5=32$ подмножества. Если пустое запрещено, остаётся $32-1=31$; если запрещено и полное, остаётся 30.

Где можно ошибиться

Параметр $k$ — размер выбора, а не номер элемента. Коэффициент сам по себе не является вероятностью и часто больше единицы. В вероятностной задаче сначала выясняют, какие исходы равновозможны, а затем делят благоприятное число на общее. За пределами $0\le k\le n$ иногда вводят соглашение о нуле; это соглашение следует назвать явно, а не вычислять факториал отрицательного числа.