Що таке комбінація (сполучення) в комбінаториці?

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

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

Сполучення (комбінація) - це вибір k елементів із n різних без урахування порядку і без повторень. Кількість таких виборів позначається C(n, k) і обчислюється за формулою: C(n, k) = n! / (k! (n − k)!), де 0 ≤ k ≤ n.

Приклад: із 5 різних книжок вибрати 2 для поїздки можна 10 способами: C(5, 2) = 10.

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

Визначення та позначення

Сполучення - це будь-яка підмножина розміру k множини з n попарно різних елементів. Позначають C(n, k), також використовують вираз «n по k» (біноміальний коефіцієнт).

Порядок не важливий.
Повторень немає (кожен елемент можна вибрати не більше одного разу).
Діапазон параметрів: 0 ≤ k ≤ n; C(n, 0) = C(n, n) = 1.

Формула: C(n, k) = n! / (k! (n − k)!). Зручний еквівалент без великих факторіалів: C(n, k) = ∏_{i=1}^{k} (n − k + i) / i, часто беруть k = min(k, n − k) для зменшення кількості ітерацій.

Коли використовувати сполучення

Вибір підкоманди/комітету зі співробітників (хто входить - важливо, порядок - ні).
Задачі виду «скільки підмножин розміру k».
Кількість способів вибрати позиції успіхів у серії незалежних випробувань.

Відмінності від інших моделей

Перестановки: порядок важливий, використовуються всі n елементів; число n!.
Розміщення без повторень: порядок важливий, беремо k із n; число A(n, k) = n! / (n − k)!.
Сполучення: порядок не важливий, беремо k із n; число C(n, k).

Приклади розрахунків

C(5, 2) = 5! / (2!·3!) = 120 / (2·6) = 10.
C(10, 3) = 10! / (3!·7!) = (8·9·10) / (2·3) = 120.
Симетрія: C(10, 7) = C(10, 3) = 120.

Властивості

Симетрія: C(n, k) = C(n, n − k).
Крайові значення: C(n, 0) = C(n, n) = 1.
Рекурсія Паскаля: C(n, k) = C(n − 1, k) + C(n − 1, k − 1).
Сума за k: ∑_{k=0}^{n} C(n, k) = 2^n (кількість усіх підмножин множини з n елементів).

Практичний розрахунок без великих факторіалів

Використовуйте мультиплікативну формулу зі скороченням на кожному кроці: послідовно множте на (n − k + i) і діліть на i, обираючи k = min(k, n − k). Це стійко і для великих n, k.

Код: обчислення C(n, k) і генерація k-сполучень (JavaScript)

function binom(n, k) {
  if (k < 0 || k > n) return 0n;
  // BigInt для точності на великих n
  let K = BigInt(k);
  let N = BigInt(n);
  if (K > N - K) K = N - K; // симетрія
  let num = 1n;
  let den = 1n;
  for (let i = 1n; i <= K; i++) {
    num *= (N - K + i);
    den *= i;
    // скорочуємо дріб за НСД, щоб числа не росли надто швидко
    const g = gcd(num, den);
    num /= g;
    den /= g;
  }
  return num / den;
}

function gcd(a, b) {
  while (b !== 0n) [a, b] = [b, a % b];
  return a;
}

// Генерація всіх k-сполучень елементів масиву arr у лексикографічному порядку
function combinations(arr, k) {
  const n = arr.length;
  if (k < 0 || k > n) return [];
  const idx = Array.from({ length: k }, (_, i) => i);
  const res = [];
  while (true) {
    res.push(idx.map(i => arr[i]));
    // Знайти позицію для збільшення
    let t = k - 1;
    while (t >= 0 && idx[t] === n - k + t) t--;
    if (t < 0) break;
    idx[t]++;
    for (let i = t + 1; i < k; i++) idx[i] = idx[i - 1] + 1;
  }
  return res;
}

// Приклади
console.log(String(binom(5, 2))); // "10"
console.log(combinations(["A", "B", "C", "D", "E"], 2));

Зв'язок з біноміальною формулою

Біноміальні коефіцієнти C(n, k) - це коефіцієнти при a^{n−k} b^{k} у розкладі (a + b)^n. Тому набір значень за фіксованим k при різних n утворює трикутник Паскаля.

Поради для співбесіди

Завжди проговорюйте критерії: порядок не важливий, повторень немає - отже, сполучення.
Швидко відрізняйте моделі: порядок важливий → перестановки/розміщення; порядок не важливий → сполучення.
Використовуйте формулу з добутком замість факторіалів, щоб уникнути переповнень і спростити обчислення на дошці.
Перевіряйте граничні випадки: k = 0, k = n, а також симетрію C(n, k) = C(n, n − k).

Підсумок: сполучення - це спосіб порахувати кількість підмножин фіксованого розміру, коли порядок не важливий і елементи не повторюються.

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

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

Premium

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