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

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

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

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

Контент

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

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

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

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

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

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

- Перелічувальна комбінаторика: підрахунок кількості об'єктів за правилами (перестановки, розміщення, сполучення, принципи суми і добутку, включення-виключення, твірні функції).
- Розбиття і розподіли: «кулі та ящики», розбиття множин і чисел, розподіли з обмеженнями.
- Імовірнісні задачі на скінченних просторах: обчислення ймовірностей через підрахунок наслідків (біноміальний і гіпергеометричний розподіли, схема Бернуллі).
- Екстремальна комбінаторика: знаходження максимуму/мінімуму дискретних структур при обмеженнях (принцип Діріхле, межі та конструкції).
- Конструктивні задачі та задачі на існування: побудувати об'єкт із заданими властивостями або довести (не)існування (часто з імовірнісним методом).
- Комбінаторна оптимізація: вибір оптимальної дискретної структури (паросполучення, покриття, маршрутизація), часто на графах.

## Докладна відповідь

### 1) Перелічувальна комбінаторика (підрахунок)

Задачі: «Скільки існує…?» Прийоми: принципи суми і добутку, перестановки (n!), розміщення A(n, k) = n!/(n−k)!, сполучення C(n, k) = n!/(k!(n−k)!), варіанти з повтореннями, включення-виключення, рекурентності та твірні функції.

- Приклад: скількома способами розсадити 5 із 10 співробітників на 5 різних місць? Відповідь: A(10, 5) = 10!/5!.
- Приклад: скількома способами вибрати 3 рев'юерів із 10? Відповідь: C(10, 3) = 120.

### 2) Розбиття і розподіли

Задачі розподілу предметів за категоріями/«ящиками» з обмеженнями (предмети розрізнювані/нерозрізнювані, ящики розрізнювані/ні, порожні ящики дозволені/заборонені), розбиття множин і чисел.

- Метод «зірки та смуги»: кількість розв'язків x1 + … + xk = n при xi ≥ 0 дорівнює C(n + k − 1, k − 1).
- Числа Стірлінга S(n, k) - розбиття множини на k непорожніх підмножин; числа Белла - усі розбиття множини.
- Приклад: роздати 7 однакових цукерок 3 дітям (порожні частки допустимі): C(7 + 3 − 1, 3 − 1) = C(9, 2) = 36.

### 3) Імовірнісні задачі на скінченних наслідках

У рівноймовірних просторах імовірність події - це відношення кількості сприятливих наслідків до загальної кількості. Часто використовуються сполучення та гіпергеометричний розподіл; у незалежних випробуваннях - схема Бернуллі та біноміальний розподіл.

- Приклад: імовірність із 52 карт у 5-картковій руці отримати рівно 2 тузи: C(4, 2) · C(48, 3) / C(52, 5).

### 4) Екстремальна комбінаторика

Шукаються найбільші/найменші можливі значення параметрів дискретних структур при обмеженнях. Використовуються принцип Діріхле, лема про рукостискання, методи двобічних оцінок, імовірнісний метод.

- Приклад: серед 13 людей знайдуться двоє, народжені в один місяць (13 > 12 за принципом Діріхле).

### 5) Конструктивні задачі та задачі на існування

Потрібно побудувати об'єкт із заданими властивостями (розфарбування графів, коди, блок-дизайни) або довести неможливість/існування. Часто застосовуються інваріанти, парність, імовірнісний метод (доведення існування без явної конструкції).

### 6) Комбінаторна оптимізація

Оптимізаційні задачі на дискретних структурах: мінімальні покриття/вершини, максимальні паросполучення, призначення, маршрутизація, розкладки. Зв'язок із графами, лінійним програмуванням і алгоритмами. У прикладному програмуванні трапляються під час планування, розподілу ресурсів, оптимізації тестів і конфігурацій.

## Основні принципи та формули (пам'ятка)

- Принцип суми: якщо об'єкти вибираються із взаємовиключних варіантів A і B, то всього |A| + |B|.
- Принцип добутку: послідовний вибір - перемноження кількості варіантів.
- Перестановки: n!; з повтореннями: n! / (r1! r2! …).
- Розміщення: A(n, k) = n! / (n − k)!.
- Сполучення: C(n, k) = n! / (k!(n − k)!).
- Сполучення з повтореннями: C(n + k − 1, k).
- Включення-виключення: |A ∪ B| = |A| + |B| − |A ∩ B|; узагальнюється на більшу кількість множин.

## Приклад: міні-утиліта для типових розрахунків (JavaScript)

```js
/* Базові функції підрахунку: перестановки, розміщення, сполучення, зірки-і-смуги та гіпергеометрична ймовірність */
function factorial(n) {
  if (n < 0 || !Number.isInteger(n)) throw new Error('n must be a non-negative integer');
  let r = 1;
  for (let i = 2; i <= n; i++) r *= i;
  return r;
}

function nPr(n, k) {
  if (k < 0 || k > n) return 0;
  let r = 1;
  for (let i = 0; i < k; i++) r *= (n - i);
  return r; // дорівнює n! / (n-k)!
}

function nCr(n, k) {
  if (k < 0 || k > n) return 0;
  k = Math.min(k, n - k);
  let res = 1;
  for (let i = 1; i <= k; i++) {
    res = (res * (n - k + i)) / i; // мультиплікативна формула стійка
  }
  return Math.round(res);
}

// «Зірки і смуги»: кількість розв'язків x1+...+xk = n, xi >= 0
function starsAndBars(n, k) {
  if (n < 0 || k <= 0) return 0;
  return nCr(n + k - 1, k - 1);
}

// Гіпергеометрична ймовірність: із N об'єктів, K «успіхів», вибираємо n без повернення, ймовірність рівно k успіхів
function hypergeom(N, K, n, k) {
  if (k < 0 || k > K || k > n || n > N) return 0;
  const favorable = nCr(K, k) * nCr(N - K, n - k);
  const total = nCr(N, n);
  return favorable / total;
}

// Приклади використання
console.log('A(10,5) розміщень:', nPr(10, 5)); // 30240
console.log('C(10,3) сполучень:', nCr(10, 3));   // 120
console.log('Перестановки 8 елементів:', factorial(8)); // 40320
console.log('Роздати 7 однакових цукерок 3 дітям:', starsAndBars(7, 3)); // 36
console.log('P(рівно 2 тузи у 5 картах):', hypergeom(52, 4, 5, 2)); // ≈ 0.0399
```

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

Для рев’юера

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

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