Біноміальний коефіцієнт

Біноміальні коефіцієнти — коефіцієнти в розкладі $\ (1+x)^{n}$ по степенях $\ x$ (так званий біном Ньютона):

Біноміальні коефіцієнти розташовані у вигляді трикутника Паскаля.

Візуалізація біноміальних коефіцієнтів до 4 степеня

$(1+x)^{n}={n \choose 0}+{n \choose 1}x+{n \choose 2}x^{2}+\cdots +{n \choose n}x^{n}=\sum _{k=0}^{n}{n \choose k}x^{k}.$

Біноміальний коефіцієнт є узагальненням кількості невпорядкованих виборів $C_{n}^{k}$, що визначена тільки для невід'ємних цілих чисел $n$, $k$, тобто $\ n+1\in \mathbb {N}$ та $\ k+1\in \mathbb {N} .$ У явному вигляді для $0\leq k\leq n$:

${n \choose k}=C_{n}^{k}={\frac {n!}{k!\;(n-k)!}}$,

де $n!$ та $k!$ — факторіали чисел $n$ і $k$.

Явні формули

Обчислюючи коефіцієнти в розкладі $(1+x)^{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}}$

де $k!$ позначає факторіал числа k.

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

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

Для цілих від'ємних показників коефіцієнти розкладу бінома $(1+x)^{-n}$ рівні

${\binom {-n}{k}}={\begin{cases}(-1)^{k}\cdot {\frac {(n+k-1)!}{k!(n-1)!}},&k\geqslant 0,\\0,&k<0.\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}},$ … є

$\sum _{k=0}^{\infty }{\binom {n}{k}}x^{k}=(1+x)^{n}.$

Для фіксованого значення k твірною функцією послідовності коефіцієнтів ${\tbinom {0}{k}},\;{\tbinom {1}{k}},\;{\tbinom {2}{k}},$ … є

$\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}},$ або $\sum _{n=0}^{\infty }\sum _{k=0}^{n}{\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$ при записі числа k в системі числення з основою p, всі розряди не перевищують відповідних розрядів числа 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)*\dots *(a_{m}+1)$, де числа $a_{1},\;\ldots ,a_{m}$ — розряди p-кового запису числа n; а число $\textstyle m=\lfloor \log _{p}{n}\rfloor +1,$ де $\lfloor \cdot \rfloor$ — функція «підлоги» — це довжина даного запису.

Тотожності

1. ${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$
2. ${n \choose k}={\frac {n}{n-k}}{n-1 \choose k}$
3. ${n \choose 0}+{n \choose 1}+\cdots +{n \choose n}=2^{n}$
4. ${n \choose 0}+{n \choose 2}+\cdots +{n \choose 2\lfloor n/2\rfloor }=2^{n-1}$
5. ${n \choose 0}^{2}+{n \choose 1}^{2}+\cdots +{n \choose n}^{2}={2n \choose n}$
6. $\sum _{k=0}^{n}{r \choose m+k}{s \choose n-k}={r+s \choose m+n}$ (згортка Вандермонда)

Біном Ньютона і наслідки

• ${n \choose 0}+{n \choose 1}+\ldots +{n \choose n}=2^{n},$ де $n\in \mathbb {N} .$
• $\sum _{i+j=m}{\binom {n}{j}}{\binom {n}{i}}(-1)^{j}={\begin{cases}{\binom {n}{m/2}},&{\text{якщо}}\ m\equiv 0{\pmod {2}},\\0,&{\text{якщо}}\ 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\in \mathbb {N} .$
• Сильніша тотожність: ${n \choose 0}+{n \choose 2}+\ldots +{n \choose 2\lfloor n/2\rfloor }=2^{n-1},$ де $n\in \mathbb {N} .$
• $\sum _{k=-a}^{a}(-1)^{k}{2a \choose k+a}^{3}={\frac {(3a)!}{(a!)^{3}}},$

а в загальнішому вигляді

$\sum _{k=-a}^{a}(-1)^{k}{a+b \choose a+k}{b+c \choose b+k}{c+a \choose c+k}={\frac {(a+b+c)!}{a!\,b!\,c!}}.$

Згортка Вандермонда і наслідки

• $\sum _{k}{r \choose m+k}{s \choose n-k}={r+s \choose m+n}$ (згортка Вандермонда), де $m,n\in \mathbb {Z} ,$ а $r,s\in \mathbb {R} .$

Це тотожність виходить обчисленням коефіцієнта при $x^{m+n}$ у розкладі $(1+x)^{r}(1+x)^{s}$ з урахуванням тотожності $(1+x)^{r+s}=(1+x)^{r}(1+x)^{s}.$ Сума береться за всіма цілими $k$, для яких $\textstyle {r \choose m+k}{s \choose n-k}\neq 0.$ Для довільних дійсних $r$, $s$ число ненульових доданків у сумі буде скінченним.

• ${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}^{n}{\frac {(-1)^{k-1}}{k}}{n \choose k}=\sum _{k=1}^{n}{\frac {1}{k}}=H_{n}$ — n- е гармонічне число.
• Мультисекція ряду $(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}}.$

• Виконуються рівності:

${\begin{alignedat}{2}{\binom {n}{3}}&={\frac {n(n-1)(n-2)}{\color {Green}2}}-\sum _{i=2}^{n-1}{(n-i)(n-i+1)}=\\&=n(n-1)(n-2)-\sum _{i=2}^{n-1}{(n-i)({\color {Green}2}n-i+1)}=\\&=3{\binom {n}{3}}-2{\binom {n}{3}};\\\end{alignedat}}$

${\begin{alignedat}{2}{\binom {n}{4}}&={\frac {n(n-1)(n-2)(n-3)}{\color {Green}2}}-\sum _{i=3}^{n-1}{(n-i)\left(n(n-1)-\sum _{i_{0}=1}^{i-2}i_{0}\right)}=\\&=n(n-1)(n-2)(n-3)-\sum _{i=3}^{n-1}{(n-i)\left({\color {Green}2}n(n-1)-\sum _{i_{0}=1}^{i-2}i_{0}\right)}=\\&=24{\binom {n}{4}}-23{\binom {n}{4}};\\\end{alignedat}}$

${\begin{alignedat}{2}{\binom {n}{5}}&={\frac {n(n-1)(n-2)(n-3)(n-4)}{\color {Green}2}}-\\&-\sum _{i=4}^{n-1}{(n-i)\left(n(n-1)(n-2)-\sum _{i_{0}=1}^{i-3}\sum _{i_{1}=1}^{i_{0}}i_{1}\right)}=\\&=n(n-1)(n-2)(n-3)(n-4)-\\&-\sum _{i=4}^{n-1}{(n-i)\left({\color {Green}2}n(n-1)(n-2)-\sum _{i_{0}=1}^{i-3}\sum _{i_{1}=1}^{i_{0}}i_{1}\right)}=\\&=120{\binom {n}{5}}-119{\binom {n}{5}}.\end{alignedat}}$

Звідки випливає:

${\binom {n}{3}}={\frac {\sum \limits _{i=2}^{n-1}{(n-i)(2n-i+1)}}{2}}={\frac {\sum \limits _{i=2}^{n-1}{(n-i)\left(2A_{n}^{1}-{\binom {i-1}{1}}\right)}}{2}};$

${\binom {n}{4}}={\frac {\sum \limits _{i=3}^{n-1}{(n-i)\left(2n(n-1)-\sum \limits _{i_{0}=1}^{i-2}i_{0}\right)}}{23}}={\frac {\sum \limits _{i=3}^{n-1}{(n-i)\left(2A_{n}^{2}-{\binom {i-1}{2}}\right)}}{23}};$

${\begin{alignedat}{2}&{\binom {n}{5}}={\frac {\sum \limits _{i=4}^{n-1}{(n-i)\left(2n(n-1)(n-2)-\sum \limits _{i_{0}=1}^{i-3}\sum \limits _{i_{1}=1}^{i_{0}}i_{1}\right)}}{119}}=\\&={\frac {\sum \limits _{i=4}^{n-1}{(n-i)\left(2A_{n}^{3}-{\binom {i-1}{3}}\right)}}{119}};\\\end{alignedat}}$

${\binom {n}{k}}={\frac {\sum \limits _{i=k-1}^{n-1}{(n-i)\left(2A_{n}^{k-2}-{\binom {i-1}{k-2}}\right)}}{k!-1}},$

де $A_{n}^{k}$ — кількість розміщень із n по k.

Матричні співвідношення

Якщо взяти квадратну матрицю, відрахувавши N елементів по катетах трикутника Паскаля і повернувши матрицю на будь-який з чотирьох кутів, то детермінант цих чотирьох матриць дорівнює ±1 за будь-якого N, причому детермінант матриці з вершиною трикутника у верхньому лівому куті дорівнює 1.

У матриці ${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$ числа на діагоналі $i+j=const$ повторюють числа рядків трикутника Паскаля $(i,j=0,1,\ldots )$. Її можна розкласти в добуток двох строго діагональних матриць: нижньотрикутної та одержуваної з неї транспонуванням. А саме:

${\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}}_{m,n}^{-1}=\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}}_{m,n}^{-1}$ ортогональний до будь-якого такого вектора.

${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{p,n}^{-1}=\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}}_{m,n}^{-1}$ дорівнює нулю. Використовуючи тотожність вище і рівність одиниці скалярного добутку нижнього рядка матриці ${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{m,n}^{-1}$ на останній стовпець матриці ${\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.$

Цілозначні многочлени

Біноміальні коефіцієнти ${\tbinom {x}{0}}=1,{\tbinom {x}{1}}=x,{\tbinom {x}{2}}={\tfrac {x^{2}}{2}}-{\tfrac {x}{2}},$ … є цілозначними многочленами від $x$, тобто, набувають цілих значень за цілих значень $x,$ — це неважко зрозуміти, наприклад, за трикутником Паскаля. Більш того, вони утворюють базис цілозначних многочленів, у якому всі цілозначні многочлени виражаються як лінійні комбінації з цілими коефіцієнтами.

Разом з тим, стандартний базис $1,x,x^{2},$ … не дозволяє виразити всіх цілочисельних многочленів, якщо використовувати тільки цілі коефіцієнти, оскільки вже ${\tbinom {x}{2}}={\tfrac {x^{2}}{2}}-{\tfrac {x}{2}}$ має дробові коефіцієнти при степенях $x$.

Цей результат узагальнюється на многочлени багатьох змінних. А саме, якщо многочлен $R(x_{1},\dots ,x_{m})$ степеня $k$ має дійсні коефіцієнти і набуває цілих значень за цілих значень змінних, то

$R(x_{1},\dots ,x_{m})=P\left({\binom {x_{1}}{1}},\dots ,{\binom {x_{1}}{k}},\dots ,{\binom {x_{m}}{1}},\dots ,{\binom {x_{m}}{k}}\right),$

де $P$ — многочлен із цілими коефіцієнтами.

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

1. ${2n \choose n}\sim {\frac {2^{2n}}{\sqrt {\pi n}}}$
2. $\sum _{k=0}^{m}{n \choose k}\leq {\frac {n}{(n/2-m)^{2}}}2^{n-3}$ при $m\leq n/2$ (нерівність Чебишева)
3. $\sum _{k=0}^{m}{n \choose k}\leq 2^{nH(m/n)}$ (ентропійна оцінка), де $H(x)=-x\log _{2}x-(1-x)\log _{2}(1-x)$ — ентропія.
4. $\sum _{k=0}^{n/2-\lambda }{n \choose k}\leq 2^{n}e^{-2\lambda ^{2}/n}$ (нерівність Чернова)

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

• Біноміальні коефіцієнти можуть бути обчислені за допомогою тотожності ${n \choose k}={n-1 \choose k}+{n-1 \choose k-1}$, якщо на кожному кроці зберігати значення ${n \choose k}$ для $k=0,1,\dots ,n$. Цей алгоритм особливо ефективний, якщо необхідно отримати всі значення ${n \choose k}$ при фіксованому $n$. Алгоритм потребує $\ O(n)$ пам'яті ($\ O(n^{2})$ для обчислення всієї таблиці) і $\ O(n^{2})$ часу.

• Інший спосіб ґрунтується на тотожності ${n \choose k}={\frac {n}{n-k}}{n-1 \choose k}$. Він дозволяє обчислити значення ${n \choose k}$ при фіксованому $k$. Алгоритм потребує $\ O(1)$ пам'яті і $\ O(k)$ часу.

Узагальнення

Оскільки для $\ n+1\in \mathbb {N} :\ n!=\Gamma (n+1)$, то значення біноміального коефіцієнта можна визначити для усіх комплексних чисел $\ n\in \mathbb {C}$ та $\ k\in \mathbb {C}$:

${n \choose k}={\frac {\Gamma (n+1)}{\Gamma (k+1)\Gamma (n-k+1)}}$

Явні формули для обчислення біноміальних коефіцієнтів для цілих чисел $\ n$ та $\ k$:

${n \choose k}={\frac {n!}{k!\;(n-k)!}}$ для $0\leq k\leq n$;

${n \choose k}=0$ для $\ k<0$ або $0\leq n<k$;

${n \choose k}=(-1)^{k}{-n+k-1 \choose k}$ для $n<0\leq k$.

Біноміальні коефіцієнти часто зустрічаються в комбінаторних задачах і теорії імовірностей.

Узагальненням біноміального коефіцієнта є поліноміальний коефіцієнт.

Генерація на C++

#include <iostream>
#include <string>

using namespace std;

void C(int n, int m, int startAt = 1, string s = "") {
	for (int i = startAt; i <= n - m + 1; i++) {
		if (1 == m)
			cout << s + (char)(i+'0') << endl;
		else
			C(n, m - 1, i + 1, s + (char)(i+'0'));
	}	
}

int main() {
	C(7, 3);
	
	return 0;
}

Див. також

• Біном
• Гауссові біноміальні коефіцієнти
• Центральний біноміальний коефіцієнт
• Функція fusc

Джерела

• Завало С. Т. (1972). Елементи аналізу. Алгебра многочленів. Київ: Радянська школа. с. 462. (укр.)