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

Визначення

Біномиальним коефіцієнтом $C_n^k$ називається кількість способів вибрати набір $k$ елементів з $n$ різних елементів без врахування порядку розташування цих елементів (тобто кількість невпрорядкованих наборів).

Також біноміальні коефіцієнти - це кофіцієнти в розкладі $(a+b)^n$ (біном Ньютона):

$$(a+b)^n = C_n^0 a^n + C_n^1 a^{n-1} b + C_n^2 a^{n-2} b^2 + \ldots + C_n^k a^{n-k} b^k + \ldots + C_n^n b^n$$

Вважається, що цю формулу, як і трикутник, що дозволяє ефективно знаходити ці коефіцієнти, відкрив Блез Паскаль (Blaise Pascal), що жив у 17 ст. Тим не менш, вона була відома ще китайскому математику Яну Хуею (Yang Hui), що жив у 13 ст. Можливо, її відкрив перський вчений Омар Хаям (Omar Khayyam). Більше того, індійський математик Пінгала (Pingala), що жив ще у 3 ст. до н.е., отримав близькі результати. Заслуга ж Ньютона полягає в тому, що він узагальнив цю формулу для степенів, що не є натуральними.

Обчислення

Аналітична формула для обчислення:

$$C_n^k = \frac{n!}{k! (n-k)!}$$

Цю формулу легко вивести із задачі про невпорядковану вибірку (кількість способів невпрорядковано вибрати $k$ елементів з $n$ елементів). Спочатку порахуємо кількість впрорядкованих вибірок. Вибрати перший елемент є $n$ способів, другий - $n-1$, третій - $n-2$, і так далі. В результаті для кількості впорядкованих вибірок отримуємо формулу: $n(n-1)(n-2) \ldots (n-k+1) = \frac{n!}{(n-k)!}$. До невпрорядкованих вибірок легко перейти, якщо замітити, що кожній невпорядкованій вибірці відповідає рівно $k!$ впорядкованих (тобто це кількість різних перестановок $k$ елементів). В результаті, при діленні $\frac{n!}{(n-k)!}$ на $k!$, ми і отримуємо шукану формулу.

Рекурсивна формула (з якою вз'язаний славнозвісний "трикутник Паскаля"):

$$C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$$

Її легко вивести через попередню формулу.

Варто замітити, що при $n<k$ значення $C_n^k$ завжди рівне нулю.

Властивості

Біноміальні коефіцієнти мають безліч різних властивостей, наведемо найбільш прості з них:

• Правило симетрії:

$$C_n^k = C_n^{n-k}$$

• Вніс-виніс:

$$C_n^k = \frac{n}{k} C_{n-1}^{k-1}$$

• Сума по $k$:

$$\sum_{k=0}^n C_n^k = 2^n$$

• Сума по $n$:

$$\sum_{m=0}^n C_m^k = C_{n+1}^{k+1}$$

• Сума по $n$ і $k$:

$$\sum_{k=0}^{m} C_{n+k}^k = C_{n+m+1}^m$$

• Сума квадратів:

$$(C_n^0)^2 + (C_n^1)^2 + \ldots + (C_n^n)^2 = C_{2n}^n$$

• Зважена сума:

$$1 C_n^1 + 2 C_n^2 + \ldots + n C_n^n = n 2^{n-1}$$

• Зв'язок з числами Фібоначчі:

$$C_n^0 + C_{n-1}^1 + \ldots + C_{n-k}^k + \ldots + C_0^n = F_{n+1}$$

Реалізація

Обчислення за допомогою аналітичної формули

Обчислення за допомогою аналітичної формули легко програмується, однак цей спосіб схильний до переповнення навіть при відносно невеликих значениях $n$ та $k$ (навіть якщо відповідь цілком поміщається в деякий тип даних, обчислення проміжних факторіалів може привести до переповненню). Тому дуже часто цей спосіб можна застосовувати тільки разом з довгою арифметикою:

int binomial_coefficient(int n, int k) {
    int res = 1;
    for (int i = n-k+1; i <= n; i++) {
        res *= i;
    }
    for (int i = 2; i <= k; i++) {
        res /= i;
    }
}

Покращена реалізація

Можна помітити, що в наведеній вище реалізації у чисельнику і знаменнику однакова кількість множників ($k$), кожний з яких не менший одиниці. Тому можна замінити наш дріб на добуток $k$ дробів. Однак, можна замітити, що після домножения поточної відповіді на кожен наступний дріб все рівно отримуватимемо ціле число (випливає з властивості "вніс-виніс"). Тому отримуємо таку реалізацію:

int binomial_coefficient(int n, int k) {
    double res = 1;
    for (int i = 1; i <= k; i++) {
        res = res * (n-k+i) / i;
    }
    return (int) (res + 0.01);
}

TODO: rewrite without double?

Вкінці перетворюємо дробове число до цілого, враховуючи, що через накопичення похибок воно може виявитися трохи меншим шуканого значення (наприклад, $2.99999$ замість $3$).

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

Використавши рекуррентне співвідношення можна побудувати таблицю біноміальних коефіцієнтів (фактично, трикутник Паскаля), і з неї брати результат. Перевага цього методу в тому, що проміжні результати ніколи не є більшими за шукане значення, і для обчислення кожного нового елементу таблиці треба всього лише одне додавання. Недоліком є повільна робота при великих $n$ та $k$, коли насправді таблица не потрібна, а потрібне лише одне шукане значення (тому що для обчислення $C_n^k$ знадобиться побудувати таблицю для всіх $C_i^j,\ \ 1 \le i \le n,\ \ 1 \le j \le n$, або хоча б до $1 \le j \le \min(i,2k)$).

const int maxn = ...;
int C[maxn+1][maxn+1];
for (int n = 0; n <= maxn; n++) {
    C[n][0] = C[n][n] = 1;
    for (int k = 1; k < n; k++) {
        C[n][k] = C[n-1][k-1] + C[n-1][k];
    }
}

Якщо вся таблица значень не потрібна, то достатньо зберігати від неї тільки два рядки (поточний - $n$-ий і попередній - $n-1$-ий).

Обчислення за $O(1)$

У деяких ситуациях виявляється вигідно заздалегідь обрахувати значення всіх факторіалів для того, щоб будь-який необхідний біноміальний коефіцієнт можна було обрахувати за допомогою лише двох ділень. Такий підхід може бути корисним при використанні довгої арифметики, коли пам'ять не дозваляє обрахувати зазделегідь весь трикутник Паскаля, або ж коли потрібно проводити розрахунки за деяким простим модулем (якщо модуль не простий, то виникають труднощі при діленні чисельника на знаменник; їх можна побороти, якщо факторизувати модуль і зберігати всі числа у вигляді векторів із степенями цих простих; див. розділ про довгу арифметику у факторизованому вигляді.

Застосування

TODO: add applications

Задачі

TODO: add problems