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