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

В математике биномиальные коэффициенты — это коэффициенты в разложении бинома Ньютона $(1+x)^n$ по степеням x. Коэффициент при $x^k$ обозначается $\textstyle\binom{n}{k}$ или $\textstyle C_n^k$ и читается «биномиальный коэффициент из n по k» (или «це из n по k»):

$(1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\ldots +\binom{n}{n}x^n=\sum_{k=0}^{n} \binom{n}{k} x^k,$

причём n здесь может быть как целым, так и произвольным действительным числом.

В комбинаторике биномиальный коэффициент $\textstyle\binom{n}{k}$ для неотрицательных целых чисел n и k интерпретируется как количество сочетаний из n по k, то есть количество всех подмножеств (выборок) размера k в n-элементном множестве.

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

Явные формулы

Значение биномиального коэффициента $\textstyle\binom{n}{k}$ определено для всех действительных чисел n и целых чисел k по формулам:

$\binom{n}{k}=\begin{cases} \frac{n(n-1)(n-2)\cdot\ldots\cdot(n-k+1)}{k!}, & k\geqslant 0,\\ 0, & k<0, \end{cases}$

где $m!$ обозначает факториал числа m.

Для неотрицательных целых n и k также справедливы формулы:

$\binom{n}{k} = \begin{cases} \frac{n!}{k!(n-k)!}, & k\leqslant n.\\ 0, & k>n. \end{cases}$

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

Тождество

${n\choose k}={n-1\choose k-1}+{n-1\choose k}$

позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел n, k в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих:

$\begin{matrix} n=0: & & & & & 1 & & & &\\ n=1: & & & & 1 & & 1 & & &\\ n=2: & & & 1 & & 2 & & 1 & &\\ n=3: & & 1 & & 3 & & 3 & & 1 &\\ n=4: & 1 & & 4 & & 6 & & 4 & & 1\\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots & \end{matrix}$

Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от выписанной здесь поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, О. Хайяму и др.).

Строки в треугольнике Паскаля в пределе стремятся к функции нормального распределения.

Свойства

Производящие функции

Для фиксированного значения n производящей функцией последовательности биномиальных коэффициентов $\tbinom{n}{0},\;\tbinom{n}{1},\;\tbinom{n}{2},\;\ldots$ является:

$\sum_k \binom{n}{k} x^k = (1+x)^n.$

Для фиксированного значения k производящей функцией последовательности биномиальных коэффициентов $\tbinom{0}{k},\;\tbinom{1}{k},\;\tbinom{2}{k},\;\ldots$ является:

$\sum_n \binom{n}{k} y^n = \frac{y^k}{(1-y)^{k+1}}.$

Двумерной производящей функцией биномиальных коэффициентов $\tbinom{n}{k}$ для целых $n,\,k$ является:

$\sum_{n,k} \binom{n}{k} x^k y^n = \frac{1}{1-y-xy}.$

Делимость

Из теоремы Люка следует, что:

• $\textstyle \binom{n}{k}$ нечётен $\iff$ в двоичной записи числа k единицы не стоят в тех разрядах, где в числе n стоят нули.
• $\textstyle \binom{n}{k}$ некратен простому p $\iff$ в p-ичной записи числа k все разряды не превосходят соответствующих разрядов числа n.
• В последовательности биномиальных коэффициентов $\textstyle \binom{n}{0},\;\binom{n}{1},\;\ldots,\;\binom{n}{n}$:
  • все числа не кратны заданному простому p $\iff$ $n=mp^k-1$, где натуральное число m < p;
  • все числа, кроме первого и последнего, кратны заданному простому p $\iff$ $n=p^k$;
  • количество нечётных чисел равно степени двойки (степень двойки равна количеству единиц в двоичной записи числа n);
  • не может быть поровну чётных и нечётных чисел;
  • количество не кратных простому p чисел равно $(a_1+1)\cdots(a_m+1)$, где числа $a_1,\;\ldots,\;a_m$ — разряды p-ичной записи числа n; а число $\textstyle m=\lfloor\log_p{n}\rfloor + 1$ — её длина.

Основные тождества

• ${n\choose k}={n-1\choose k-1}+{n-1\choose k}.$
• $\binom{n}{k}=(-1)^k\binom{-n+k-1}{k}.$
• ${n\choose k}={n\choose n-k}$ (правило симметрии).
• ${n\choose k}=\frac{n}{k}{n-1\choose k-1}$ (вынесение за скобки).
• ${n\choose m}{m\choose k}={n\choose k}{n-k\choose m-k}$ (замена индексов).

Бином Ньютона и следствия

• ${n\choose 0}+{n\choose 1}+\ldots+{n\choose n}=2^n.$
• $\sum_{i+j=m}\binom{n}{j}\binom{n}{i}(-1)^j= \begin{cases} (-1)^{m/2} \binom{n}{m/2} & \text{if}\ m\equiv 0\pmod{2},\\ 0 & \text{if}\ m\equiv 1\pmod{2}. \end{cases}$
• $\sum_{j=k}^{n} \binom{n}{j} (-1)^j = (-1)^k \binom{n-1}{k-1}.$
• ${n\choose 0}-{n\choose 1}+\ldots+(-1)^n{n\choose n}=0.$ Это тождество можно усилить:
• ${n\choose 0}+{n\choose 2}+\ldots+{n\choose 2\lfloor n/2\rfloor}=2^{n-1}.$

Свёртка Вандермонда и следствия

• $\sum_{k=-\infty}^{+\infty}{r\choose m+k}{s\choose n-k}={r+s\choose m+n}$ (свёртка Вандермонда).
• ${n\choose 0}{a\choose a}-{n\choose 1}{a+1\choose a}+\ldots+(-1)^n{n\choose n}{a+n\choose a}=(-1)^n{a\choose n}$.
• $\sum_{i=0}^{p} (-1)^i{p\choose i}\prod_{m=1}^{n} {i+s_m\choose s_m} =0$, если $\sum_{m=1}^n{s_m} <p$, — более общий вид тождества выше.
• ${n\choose 0}^2+{n\choose 1}^2+\ldots+{n\choose n}^2={2n\choose n}.$

Другие тождества

• $\sum_{k=1}^m \frac{(-1)^{k-1}}{k}{m \choose k}=\sum_{k=1}^m \frac{1}{k} = H_m$ — m-ое гармоническое число.
• Мультисекция ряда $(1+x)^n$ даёт тождество, выражающее сумму биномиальных коэффициентов с произвольным шагом s и смещением t $(0\leqslant t<s)$ в виде замкнутой суммы из s слагаемых:

$\binom{n}{t}+\binom{n}{t+s}+\binom{n}{t+2s}+\ldots=\frac{1}{s}\sum_{j=0}^{s-1}\left(2\cos\frac{\pi j}{s}\right)^n\cos\frac{\pi(n-2t)j}{s}.$

Матричные соотношения

Если взять квадратную матрицу, отсчитав N элементов по катетам треугольника Паскаля и повернув матрицу на любой из четырёх углов, то детерминант этих четырёх матриц равен ±1 при любом N, причём детерминант матрицы с вершиной треугольника в верхнем левом углу равен 1.

В матрице $\begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix}$ числа на диагонали i + j = const повторяют числа строк треугольника Паскаля (i, j = 0,1,…). Её можно разложить в произведение двух строго диагональных матриц: нижнетреугольной и получаемой из неё транспонированием. А именно:

$\begin{bmatrix}\binom{i+j}{i}\end{bmatrix} = UU^T,$

где $U=\begin{bmatrix}\tbinom{i}{j}\end{bmatrix}$. Обратная матрица к U имеет вид:

$U^{-1}=\begin{bmatrix}(-1)^{i+j}\binom{i}{j}\end{bmatrix}.$

Таким образом, можно разложить обратную матрицу к $\begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix}$ в произведение двух строго диагональных матриц: первая матрица — верхнетреугольная, а вторая получается из первой путем транспонирования, что позволяет дать явное выражение для обратных элементов:

$\begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{m,n}=\sum_{k=0}^{p}(-1)^{m+n}\binom{k}{m}\binom{k}{n}$, где i, j , m, n = 0..p.

Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы $\begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix}$, недостаточно приписать новую строку и столбец. Столбец j матрицы $\begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix}$ есть многочлен степени j по аргументу i, следовательно, первые p столбцов образуют полный базис в пространстве векторов длины p+1, чьи координаты могут быть интерполированы многочленом равной или меньшей степени p-1. Нижняя строка матрицы $\begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{m,n}$ ортогональна любому такому вектору.

$\begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{p,n}=\sum_{k=0}^{p}(-1)^{p+n}\binom{k}{p}\binom{k}{n} = (-1)^{p+n}\binom{p}{n}$

$\sum_{n=0}^{p}(-1)^{p+n}\binom{p}{n}{P}_{a}(n) = 0$ при $a<p$, где ${P}_{a}(n)$ многочлен степени a.

Если произвольный вектор длины $p+1$ можно интерполировать многочленом степени $i < p$, то скалярное произведение со строками $i+1, i+2, \dots, p$ (нумерация с 0) матрицы $\begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{m,n}$ равно нулю. Используя тождество выше и равенство единицы скалярного произведения нижней строки матрицы $\begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{m,n}$ на последний столбец матрицы $\begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix}$, получаем:

$\sum_{n=0}^{p}(-1)^{p+n}\binom{p}{n}{n}^{p} = p!.$

Для показателя большего p можно задать рекуррентную формулу:

$\sum_{n=0}^{p}(-1)^{p+n}\binom{p}{n}{n}^{p+a} = p!{P}_{2a}(p)={f}_{a}(p),$

где многочлен

${P}_{2a+2}(p) = \sum_{x=1}^{p} x{P}_{2a}(x);\quad a\geqslant 0;\quad {P}_{0}(p)=1.$

Для доказательства сперва доказывается тождество:

${f}_{a}(p+1)=\sum_{x=0}^{a} {(p+1)}^{x+1}{f}_{a-x}(p).$

Если требуется найти формулу не для всех показателей степени, то

${P}_{2a}(p) = \frac{p}{{2}^{a}}\binom{p+a}{a}{Q}_{a-1}(p);\quad a>0.$

Старший коэффициент ${Q}_{a-1}(p)$ равен 1, потребуется a-1 значений, чтобы найти другие коэффициенты:

${Q}_{a-1}(p)=p(p+1){T}_{a-3}(p)$ для $a\equiv 1\pmod{2}; a\geqslant 3.$

Асимптотика и оценки

• ${2n\choose n}\sim\frac{2^{2n}}{\sqrt{\pi n}}.$
• $\sum^{m}_{k=0}{n\choose k}\leqslant\frac{n}{(n/2-m)^2}2^{n-3}$ при $m<n/2$ (неравенство Чебышёва).
• $\sum\limits_{i = 0}^{m}{n\choose i}\leqslant 2^{nH(m/n)}$, при $m \le \frac{n}{2}$ (энтропийная оценка),

где $H(x)=-x\log_2x-(1-x)\log_2(1-x)$ — энтропия.

• $\sum^{n/2-\lambda}_{k=0}{n\choose k}\leqslant 2^ne^{-2\lambda^2/n}$ (неравенство Чернова).

Алгоритмы вычисления

Биномиальные коэффициенты могут быть вычислены с помощью формулы $\tbinom{n}{k}=\tbinom{n-1}{k}+\tbinom{n-1}{k-1}$, если на каждом шаге хранить значения $\tbinom{n}{k}$ при $k=0,\;1,\;\ldots,\;n$. Этот алгоритм особенно эффективен, если нужно получить все значения $\tbinom{n}{k}$ при фиксированном $n$. Алгоритм требует $O(n)$ памяти ($O(n^2)$ при вычислении всей таблицы биномиальных коэффициентов) и $O(n^2)$ времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени).

При фиксированном значении k биномиальные коэффициенты могут быть вычислены по рекуррентной формуле $\tbinom{n}{k}=\frac{n}{n-k}\tbinom{n-1}{k}$ с начальным значением $\tbinom{k}{k}=1$. Для вычисления значения $\tbinom{n}{k}$ этот метод требует $O(1)$ памяти и $O(n)$ времени.

См. также

• Биномиальное распределение
• Бином Ньютона
• История комбинаторики
• Композиция (теория чисел)
• Пирамида Паскаля
• Разбиение числа
• Треугольник Паскаля
• Треугольное число

Ссылки

• Фукс Д., Фукс М. Арифметика биномиальных коэффициентов // Квант. — 1970. — № 6. — С. 17—25.
• Кузьмин О. В. Треугольник и пирамида Паскаля: свойства и обобщения // Соросовский Образовательный Журнал. — 2000. — Т. 6. — № 5. — С. 101—109.
• Ландо С. К. Теневое исчисление // VIII летняя школа «Современная математика». — Дубна, 2008.
• Винберг Э. Б. Удивительные арифметические свойства биномиальных коэффициентов // Математическое просвещение. — 2008. — В. 12. — С. 33–42.
• Дональд Кнут, Роналд Грэхем, Орен Паташник Конкретная математика. Математические основы информатики = Concrete Mathematics. A Foundation for Computer Science. — 2-е. — М.: Мир; Бином. Лаборатория знаний; «Вильямс», 1998 — 2009. — 703, 784 с. — ISBN 95-94774-560-7, 78-5-8459-1588-7