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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Біноміальні коефіцієнти — коефіцієнти в розкладі \ (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;
}

Див. також[ред.ред. код]