Скількома способами можна вишикувати 5 осіб у чергу? Скільки різних кодів PIN можна утворити з цифр 0–9? Скількома способами можна вибрати 6 чисел з 49 у Lotto? На ці запитання відповідає комбінаторика — розділ математики, що займається підрахунком можливих розташувань, виборів і груп. Дізнайтеся про чотири ключові формули та навчіться застосовувати їх на практиці.
Перш ніж почати: поняття факторіала
Усі комбінаторні формули базуються на понятті факторіала (n!), тобто добутку всіх натуральних чисел від 1 до n:
n! = 1 × 2 × 3 × … × n
Приклади: 3! = 6, 4! = 24, 5! = 120, 6! = 720, 10! = 3 628 800. Приймається, що 0! = 1.
Факторіал зростає надзвичайно швидко — тому комбінаторика часто дає несподівано великі числа.
1. Перестановки — порядок має значення, всі елементи
Перестановка — це розташування всіх n елементів множини у визначеному порядку. Рахується порядок — кожне інше розташування є новою перестановкою.
Формула: P(n) = n!
Приклад
Скількома способами можна вишикувати 4 особи (Анна, Бартек, Целіна, Дарек) у чергу до каси?
P(4) = 4! = 4 × 3 × 2 × 1 = 24 способи
Інтуїція: на першому місці може стати кожна з 4 осіб, на другому — кожна з решти 3, на третьому — одна з 2, на останньому — 1. Множимо: 4 × 3 × 2 × 1 = 24.
Перестановки з повтореннями
Якщо деякі елементи повторюються (наприклад, літери в слові), ділимо на факторіали повторень:
P = n! ÷ (k₁! × k₂! × … × km!)
Приклад: скільки різних слів можна скласти з букв слова «АЛА»? n = 3, літера А повторюється 2 рази: P = 3! ÷ 2! = 6 ÷ 2 = 3 (АЛА, ААЛ, ЛАА)
2. Розміщення без повторень — порядок має значення, вибираємо k з n
Розміщення без повторень — це вибір k елементів із n, при якому порядок має значення і жоден елемент не може повторюватися.
Формула: V(n,k) = n! ÷ (n−k)!
Приклад
З 6 бігунів обираємо золоту, срібну і бронзову медалі. Скільки можливих результатів?
V(6,3) = 6! ÷ (6−3)! = 720 ÷ 6 = 120 можливостей
Інакше: 6 виборів на 1-е місце × 5 на 2-е × 4 на 3-є = 120.
Розміщення з повтореннями
Якщо елемент може повторюватися (наприклад, цифри в PIN-коді), формула спрощується до:
W(n,k) = nk
Приклад: скільки 4-значних PIN-кодів можна створити з цифр 0–9 (з повтореннями)?
W(10,4) = 10⁴ = 10 000 кодів
3. Комбінації без повторень — порядок НЕ має значення
Комбінація — це вибір k елементів із n, при якому порядок вибору не має значення — рахується лише склад групи.
Формула: C(n,k) = n! ÷ (k! × (n−k)!)
Цей символ часто записують як «n над k» або nCk. У Польщі також використовують позначення C(n,k) або символ біноміальний.
Приклад — Lotto
У Lotto жеребкують 6 чисел з 49. Скільки різних наборів можна виграти?
C(49,6) = 49! ÷ (6! × 43!) = 13 983 816
Шанс на влучення «шістки» становить 1 до ~14 мільйонів — статистично менший, ніж загинути від удару блискавки протягом року.
Шкільний приклад
З класу з 10 осіб обираємо комісію з 3 осіб. Скільки можливих комісій?
C(10,3) = 10! ÷ (3! × 7!) = 720 ÷ (6 × 5040) → C(10,3) = (10 × 9 × 8) ÷ (3 × 2 × 1) = 720 ÷ 6 = 120 комісій
4. Комбінації з повтореннями
Застосовуються рідше — коли вибираємо k елементів із n видів, і кожен вид може повторюватися, але порядок не має значення (наприклад, скількома способами можна вибрати 3 фрукти серед яблук, груш і слив, якщо фрукти одного виду ідентичні?).
Формула: CR(n,k) = C(n+k−1, k) = (n+k−1)! ÷ (k! × (n−1)!)
Приклад: скількома способами можна вибрати 3 фрукти серед 4 видів (з повтореннями)?
CR(4,3) = C(6,3) = 6! ÷ (3! × 3!) = 720 ÷ 36 = 20 способів
Як розрізнити, яку формулу застосувати?
- Чи порядок має значення? ТАК → перестановка або розміщення; НІ → комбінація
- Чи беремо всі елементи, чи лише частину? ВСІ → перестановка; ЧАСТИНУ → розміщення або комбінація
- Чи елементи можуть повторюватися? Оберіть відповідний варіант «з повтореннями»
Практичні застосування комбінаторики
- Lotto і лотереї: комбінації без повторень (шанс на виграш)
- PIN-коди і паролі: розміщення з повтореннями (сила пароля)
- Розклади і черговість: перестановки (планування завдань, турніри)
- Вибори і голосування: комбінації (кількість можливих складів команди)
- Криптографія: комбінаторика — фундамент безпеки шифрів