Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Як обчислити кількість сполучень із n по k?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

Кількість сполучень із 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)

```js
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)

```js
// Сполучення за модулем простого 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);
}

// Приклад:
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.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати741 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.