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

Біноміальні коефіцієнти — коефіцієнти в розкладі $\ (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^k_n$, що визначена тільки для невід'ємних цілих чисел $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^{m}_{k=0}{n\choose k}\le \frac{n}{(n/2-m)^2}2^{n-3}$ при $m\le n/2$ (нерівність Чебишева)
3. $\sum^{m}_{k=0}{n\choose k}\le 2^{nH(m/n)}$ (ентропійна оцінка), де $H(x)=-x\log_2x-(1-x)\log_2(1-x)$ — ентропія.
4. $\sum^{n/2-\lambda}_{k=0}{n\choose k} \le 2^ne^{-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;
}

Див. також

• Біном