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

Обозначение ${\displaystyle {\tbinom {n}{k}}}$ было введено Андреасом фон Эттингсхаузеном в 1826 году^[1], хотя сами числа были известны намного раньше. Около 1150 года индийский математик Бхаскара (санскр. Bhāskara) привёл разъяснение биномиальных коэффициентов в книге «Лилавати»^[2].

Альтернативные обозначения включают C(n,k), {}_nC_k, ^nC_k, и другие, в которых C происходит от слова «комбинации» или «выборки» (англ. combinations, англ. choices). Многие калькуляторы используют такие обозначения, поскольку они легко помещаются на однострочном дисплее. Подобные обозначения удобно сравнивать с числами перестановок, обозначаемыми как P(n,k).

Для натуральных чисел (включая 0) n и k, биномиальный коэффициент ${\displaystyle {\tbinom {n}{k}}}$ определяется как коэффициент при мономе X^k в разложении (1+X)^n. Тот же коэффициент возникает (если k \leq n) в биномиальной формуле:

${\displaystyle (x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n-k}}$

(верно для произвольных элементов x, y коммутативного кольца), — откуда и название «биномиальный коэффициент».

В комбинаторике биномиальный коэффициент выражает количество способов выбрать (без учёта порядка) k объектов из n. Это число можно получить тем же способом, что и определение через разложение бинома, если проанализировать все варианты выбора из n сомножителей выражения (1+X)^n. Существуют и другие комбинаторные интерпретации: например, количество слов из n битов с суммой k равно ${\displaystyle {\tbinom {n}{k}}}$, а число решений уравнения ${\displaystyle k=a_{1}+a_{2}+\cdots +a_{n}}$ при неотрицательных целых a_i задаётся формулой ${\displaystyle {\binom {n+k-1}{n-1}}}$.

Существует несколько способов вычисления ${\displaystyle {\tbinom {n}{k}}}$ без полного разложения бинома или явного перечисления вариантов.

Один из способов — использование рекуррентного соотношения: ${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}}$ для целых 1 \leq k < n, с граничными условиями: ${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1}$ при n \geq 0.

Эта формула легко объясняется разбиением выбора на те подмножества, которые содержат конкретный элемент, и те, которые не содержат. Для k > n или k < 0 определяют ${\displaystyle {\binom {n}{k}}=0}$.

Другой метод вычисления биномиальных коэффициентов: ${\displaystyle {\binom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1}}=\prod _{i=1}^{k}{\frac {n+1-i}{i}},}$ где числитель — число способов выбрать упорядоченную последовательность k различных элементов из n, а знаменатель поправляет на неучёт порядка.

Благодаря симметрии по k и n-k, продукт можно ограничить до меньшего из них.

Компактная формула (наиболее используемая в доказательствах): ${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}}$ для 0 \leq k \leq n.

Формула также даёт симметрию: ${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}.}$

Мультипликативная формула позволяет определять биномиальные коэффициенты для произвольного числа α: ${\displaystyle {\binom {\alpha }{k}}={\frac {\alpha (\alpha -1)\cdots (\alpha -k+1)}{k!}}}$ для k \in \mathbb{N}.

Обобщённая биномиальная формула: ${\displaystyle (1+X)^{\alpha }=\sum _{k=0}^{\infty }{\binom {\alpha }{k}}X^{k}}$ справедлива для произвольных комплексных α, |X| < 1.

Треугольник Паскаля строится по правилу:

${\displaystyle {n \choose k}+{n \choose k+1}={n+1 \choose k+1}.}$

Строка с номером n содержит числа ${\displaystyle {\tbinom {n}{k}}}$ при 0, …, n — по краям единицы, внутренние числа получаются суммированием двух расположенных выше.

Биномиальные коэффициенты широко используются в комбинаторике:

• ${\displaystyle {\tbinom {n}{k}}}$ — число способов выбрать k элементов из n.
• ${\displaystyle {\tbinom {n+k-1}{k}}}$ — количество способов выбрать k элементов с повторениями из n элементов (мультимножества).
• ${\displaystyle {\tbinom {n+k}{k}}}$ — количество строк из k единиц и n нулей.
• ${\displaystyle {\tbinom {n+1}{k}}}$ — количество строк из k единиц и n нулей, в которых нет двух подряд стоящих единиц^[3].
• Числа Каталана: ${\displaystyle {\frac {1}{n+1}}{\tbinom {2n}{n}}}$.
• Биномиальное распределение: ${\displaystyle {\tbinom {n}{k}}p^{k}(1-p)^{n-k}}$.

Для каждого неотрицательного целого k выражение ${\displaystyle {\binom {t}{k}}={\frac {t(t-1)\cdots (t-k+1)}{k!}}}$ представляет собой многочлен от t с рациональными коэффициентами.

Биномиальные коэффициенты с любым первым аргументом (действительным или комплексным числом) возникают в обобщённых версиях биномиальной теоремы.

Любой многочлен степени не выше d над полем характеристики 0 может быть представлен в виде линейной комбинации биномиальных коэффициентов: ${\displaystyle p(t)=\sum _{k=0}^{d}a_{k}{\binom {t}{k}}}$.

Из факториальной формулы следуют различные связи соседних биномиальных коэффициентов. Например, ${\displaystyle {\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}}$.

Сумма биномиальных коэффициентов в строке: ${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}=2^{n}.}$ Суммы с весом k или k²: ${\displaystyle \sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1},\quad \sum _{k=0}^{n}k^{2}{\binom {n}{k}}=(n+n^{2})2^{n-2}}$.

Также справедлива тождественность Чу-Вандермонда: ${\displaystyle \sum _{j=0}^{k}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n}{k}}.}$

Для конкретных значений индексов биномиальные коэффициенты выражаются через числа Фибоначчи: ${\displaystyle \sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n-k}{k}}=F(n+1)}$, где F — числа Фибоначчи.

• 0}^{\infty} \binom{n}{k} x^k = (1+x)^n
• Генерирующая по n: 0}^{\infty} \binom{n}{k} y^n = y^k/(1-y)^{k+1

Если n — простое, то все внутренние биномиальные коэффициенты делятся на n: ${\displaystyle {\binom {n}{1}},{\binom {n}{2}},...,{\binom {n}{n-1}}}$. Если n составное, то всегда найдётся значение k, при котором ${\displaystyle {\binom {n}{k}}}$ не делится на n.

Делимость и асимптотику биномиальных коэффициентов подробно описывают теорема Куммера и теорема Лукаса. Также биномиальные коэффициенты тесно связаны с наибольшими общими кратными последовательностей целых чисел^[4].

Биномиальные коэффициенты обобщаются до мультибиномиальных:

${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{r}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{r}!}},\quad \sum _{i=1}^{r}k_{i}=n.}$

Они являются коэффициентами при разложении (x_1 + \cdots + x_r)^n.

Для комплексных аргументов биномиальный коэффициент определяется через гамма-функцию: ${\displaystyle {x \choose y}={\frac {\Gamma (x+1)}{\Gamma (y+1)\Gamma (x-y+1)}}}$.