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

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

$(1+x)^{n}={n \choose 0}x^{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}.$$(1+x)^{n}={n \choose 0}x^{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}.$

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

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

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

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

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

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

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

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

Тотожності

1. ${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$
2. ${n \choose k}={\frac {n}{n-k}}{n-1 \choose k}$${n \choose k}={\frac {n}{n-k}}{n-1 \choose k}$
3. ${n \choose 0}+{n \choose 1}+\cdots +{n \choose n}=2^{n}$${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}$${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}$${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}$$\sum _{k=0}^{n}{r \choose m+k}{s \choose n-k}={r+s \choose m+n}$ (згортка Вандермонда)

Трикутник Паскаля

Докладніше у статті Трикутник Паскаля

Тотожність ${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$ дозволяє розташувати біноміальні коефіцієнти для невід'ємних $n$$n$, $k$$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}}$${\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°. Таблиці для зображення біноміальних коефіцієнтів були відомі й раніше.

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

1. ${2n \choose n}\sim {\frac {2^{2n}}{\sqrt {\pi n}}}$${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}$$\sum _{k=0}^{m}{n \choose k}\leq {\frac {n}{(n/2-m)^{2}}}2^{n-3}$ при $m\leq n/2$$m\leq n/2$ (нерівність Чебишева)
3. $\sum _{k=0}^{m}{n \choose k}\leq 2^{nH(m/n)}$$\sum _{k=0}^{m}{n \choose k}\leq 2^{nH(m/n)}$ (ентропійна оцінка), де $H(x)=-x\log _{2}x-(1-x)\log _{2}(1-x)$$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}$$\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}={n-1 \choose k}+{n-1 \choose k-1}$, якщо на кожному кроці зберігати значення ${n \choose k}$${n \choose k}$ для $k=0,1,\dots ,n$$k=0,1,\dots ,n$. Цей алгоритм особливо ефективний, якщо необхідно отримати всі значення ${n \choose k}$${n \choose k}$ при фіксованому $n$$n$. Алгоритм потребує $\ O(n)$$\ O(n)$ пам'яті ($\ O(n^{2})$$\ O(n^{2})$ для обчислення всієї таблиці) і $\ O(n^{2})$$\ O(n^{2})$ часу.

• Інший спосіб ґрунтується на тотожності ${n \choose k}={\frac {n}{n-k}}{n-1 \choose k}$${n \choose k}={\frac {n}{n-k}}{n-1 \choose k}$. Він дозволяє обчислити значення ${n \choose k}$${n \choose k}$ при фіксованому $k$$k$. Алгоритм потребує $\ O(1)$$\ O(1)$ пам'яті і $\ O(k)$$\ O(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+48) << endl;
		else
			C(n, m - 1, i + 1, s + (char)(i+48));
	}	
}

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

Див. також

• Біном