Комбінаторний аналіз (сполуки, перестановки, розміщення; включення-виключення)

📌 Про що ця тема

Комбінаторика відповідає на питання «скількома способами?»: вибрати, розставити, скомбінувати елементи. На іспиті перевіряють уміння розпізнати тип задачі (перестановка / розміщення / сполука) і правильно порахувати кількість варіантів. Ключове поняття — факторіал і три основні формули.

📖 Головне

• Факторіал: n! = 1·2·3·…·n. Домовленість: 0! = 1. Це кількість способів розставити n різних елементів.

• Правило суми: якщо дію можна виконати або способом А (m варіантів), або способом Б (k варіантів), і вони не перетинаються, то всього m + k.

• Правило добутку: якщо дія складається з кількох кроків (перший — m варіантів, другий — k), то всього m·k. Основа майже всіх задач.

• Перестановки Pₙ = n! — кількість способів упорядкувати всі n різних елементів (усі елементи беруться, важливий порядок).

• Розміщення Aₙᵏ = n!/(n−k)! — вибір k елементів із n, де ПОРЯДОК ВАЖЛИВИЙ (вибрали й розставили).

• Сполуки (комбінації) Cₙᵏ = n!/(k!·(n−k)!) — вибір k елементів із n, де порядок НЕ важливий.

• Зв’язок: Cₙᵏ = Aₙᵏ/k! (сполука не враховує k! порядків одного набору).

• Властивості сполук: Cₙ⁰ = Cₙⁿ = 1; Cₙ¹ = n; Cₙᵏ = Cₙⁿ⁻ᵏ (симетрія).

• Як відрізнити: беруть усі елементи → перестановка; частину з порядком → розміщення; частину без порядку → сполука.

• Включення-виключення (для двох множин): |A∪B| = |A| + |B| − |A∩B|. Віднімаємо перетин, бо він порахований двічі.

• Для трьох множин: |A∪B∪C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|.

🔢 Як це працює на прикладі

Приклад 1. З 10 учнів треба обрати 3 у команду. Порядок не важливий → сполуки:

C₁₀³ = 10!/(3!·7!) = (10·9·8)/(1·2·3) = 720/6 = 120 способів.

Якщо ж обрати 3 на посади капітан-заступник-секретар (порядок важливий) → розміщення:

A₁₀³ = 10·9·8 = 720 способів.

Приклад 2. У групі 30 осіб: 18 знають англійську, 15 — німецьку, 7 — обидві. Скільки знають хоч одну?

|A∪B| = 18 + 15 − 7 = 26. Жодної не знають: 30 − 26 = 4.

⚠️ Типові помилки

• Плутають розміщення й сполуки: якщо в умові важливо, ХТО на якому місці (посади, призові місця) — це розміщення, а не сполука.

• Забувають 0! = 1 і отримують помилку при n = k.

• У включенні-виключенні не віднімають перетин або віднімають його двічі.

• Застосовують правило суми замість добутку (коли кроки послідовні — множать, а не додають).

• Помилка в скороченні дробу з факторіалами: n!/(n−k)! = n·(n−1)·…·(n−k+1), а не n!−(n−k)!.

🎯 Що завчити напамʼять

• Pₙ = n!

• Aₙᵏ = n!/(n−k)!

• Cₙᵏ = n!/(k!·(n−k)!)

• 0! = 1; Cₙᵏ = Cₙⁿ⁻ᵏ

• |A∪B| = |A|+|B|−|A∩B|

• Правило суми (або → +), правило добутку (і → ×)

🧠 Перевір себе

1. Скількома способами 5 книг розставити на полиці?

2. Із 7 кольорів обрати 2 для прапора (порядок не важливий) — скільки варіантів?

3. Скількома способами з 6 людей обрати голову й секретаря?

4. У класі 25 учнів: 12 ходять на футбол, 10 на шахи, 5 на обидва. Скільки не ходять нікуди?

Відповіді: 1 — P₅ = 5! = 120; 2 — C₇² = 21; 3 — A₆² = 6·5 = 30; 4 — 25 − (12+10−5) = 25 − 17 = 8.