Як обчислити кількість сполучень із n по k?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Кількість сполучень із n по k (позначається C(n, k)) обчислюється за формулою: C(n, k) = n! / (k! · (n − k)!). Також зручні еквіваленти: C(n, k) = C(n, n−k), C(n, k) = C(n−1, k) + C(n−1, k−1), C(n, k) = ∏_{i=1..k} (n−k+i)/i.

Докладне пояснення

Визначення та формули

Факторіальна формула: C(n, k) = n! / (k! · (n − k)!), де n і k - невід'ємні цілі, k ≤ n.
Симетрія: C(n, k) = C(n, n−k). Завжди вигідно брати k = min(k, n−k), щоб зменшити кількість операцій.
Рекурентна формула (трикутник Паскаля): C(n, k) = C(n−1, k) + C(n−1, k−1), з базами C(n, 0) = C(n, n) = 1.
Ітеративна формула «помножити-і-поділити» (стійка до переповнень при використанні великих цілих): C(n, k) = ∏_{i=1..k} (n−k+i)/i. Ділення на кожному кроці цілочисельне.

Розбір на прикладі

Приклад: C(5, 2). За визначенням: 5! / (2! · 3!) = 120 / (2 · 6) = 120 / 12 = 10.

Через добуток: k = 2, отже C(5, 2) = ((5−2+1)/1) · ((5−2+2)/2) = (4/1) · (5/2) = 4 · 2.5 = 10 (послідовне цілочисельне ділення на кроці дає ціле значення).

Алгоритми обчислення на практиці

Через факторіали напряму. Просто, але швидко переповнюється в стандартних числах і потребує довгої арифметики. Підходить лише для дуже малих n.
Ітеративний метод (бажано): послідовно множимо на (n−k+i) і ділимо на i при i = 1..k. Використовуйте BigInt (JS) або bigint-типи, щоб уникнути переповнення.
ДП за трикутником Паскаля: O(n·k) за часом. Корисно, коли потрібно багато значень одразу, а n не надто велике; можна зберігати лише один рядок (O(k) пам'яті).
За модулем простого p. Якщо p > n, можна множити по кроках і ділити через обернені елементи за модулем p (теорема Ферма). Якщо p ≤ n, потрібні спеціальні методи (наприклад, теорема Лукаса).

Код: над цілими числами (BigInt, JavaScript)

function comb(n, k) {
  if (!Number.isInteger(n) || !Number.isInteger(k)) {
    throw new TypeError("n і k мають бути цілими числами");
  }
  if (n < 0 || k < 0 || k > n) return 0n;
  // Симетрія: C(n, k) = C(n, n-k)
  k = Math.min(k, n - k);
  let N = BigInt(n);
  let K = BigInt(k);
  let res = 1n;
  for (let i = 1n; i <= K; i++) {
    res = (res * (N - K + i)) / i; // Ділення завжди ціле
  }
  return res; // BigInt
}

// Приклади:
console.log(comb(5, 2).toString());    // "10"
console.log(comb(52, 5).toString());   // "2598960"
console.log(comb(100, 50).toString()); // "100891344545564193334812497256"

Код: за модулем простого p (коректно, коли p > n)

// Сполучення за модулем простого p, коректно, коли p > n
function modPow(a, e, p) {
  a = BigInt(a) % BigInt(p);
  e = BigInt(e);
  p = BigInt(p);
  let r = 1n;
  while (e > 0n) {
    if (e & 1n) r = (r * a) % p;
    a = (a * a) % p;
    e >>= 1n;
  }
  return r;
}

function modInv(a, p) {
  // p - просте; обернений за малою теоремою Ферма
  return modPow(a, BigInt(p) - 2n, p);
}

function combModPrime(n, k, p) {
  if (!Number.isInteger(n) || !Number.isInteger(k)) {
    throw new TypeError("n і k мають бути цілими числами");
  }
  if (n < 0 || k < 0 || k > n) return 0n;
  if (p <= n) {
    throw new Error("Цей метод коректний, лише якщо p > n. Для загального випадку використовуйте, наприклад, теорему Лукаса.");
  }
  k = Math.min(k, n - k);
  let N = BigInt(n);
  let K = BigInt(k);
  let P = BigInt(p);
  let res = 1n;
  for (let i = 1n; i <= K; i++) {
    res = (res * (N - K + i)) % P;
    res = (res * modInv(i, P)) % P;
  }
  return res;
}

// Приклад:
console.log(combModPrime(5, 2, 1000000007n).toString()); // "10"

Підводні камені та рекомендації

Переповнення: майже всі C(n, k) швидко виходять за межі 64-бітних чисел; у JS використовуйте BigInt.
Не використовуйте арифметику з плаваючою комою для ділення - отримаєте помилки округлення. Ділення має бути цілочисельним на кожному кроці.
Скорочуйте k до min(k, n−k) - це знижує кількість операцій приблизно вдвічі.
Межі: якщо k < 0 або k > n - результат 0; якщо k = 0 або k = n - результат 1.

Перевірочні значення

C(0, 0) = 1; C(1, 0) = 1; C(1, 1) = 1.
C(5, 2) = 10; C(10, 1) = 10; C(10, 9) = 10.
C(52, 5) = 2 598 960.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.