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

Матеріал з Вікіпедії — вільної енциклопедії.

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

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

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

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

Зміст

[ред.] Трикутник Паскаля

Тотожність

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

[ред.] Асимптотика і оцінки

  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) = − xlog2x − (1 − x)log2(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(n2) для обчислення всієї таблиці) і O(n2) часу (припускаючи, що кожне число займає однакову кількість пам'яті і операції з числами виконуються за одиницю часу).

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