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

Біноміальні коефіцієнти — коефіцієнти в розкладі $\ (1+x)^{n}$ по степеням $\ 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}.$

Значення біноміального коефіцієнта ${n \choose k}$ визначено для усіх цілих чисел $\ 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$,

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

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

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

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

Тотожності

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 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°. Таблиці для зображення біноміальних коефіцієнтів були відомі й раніше.

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

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)$ часу.

Генерація на 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;
}

Див. також

• Біном