Комбінаторика: перестановки, розміщення, комбінації

Комбінаторика: перестановки, розміщення, комбінації

Комбінаторика — це розділ математики, який відповідає на питання «скількома способами?». Її вивчають у 9 класі й повертаються до неї в 11-му перед НМТ, бо без неї не працює теорія ймовірностей: щоб порахувати ймовірність, треба спершу порахувати кількість варіантів. Формул тут усього три, і вони прості. Складність в іншому — учні не можуть визначити, яку саме з трьох брати. На заняттях у Tutor-Math ми ставимо це питання ребром із самого початку: спочатку критерій вибору формули, потім самі формули.

Два базові правила: сума і добуток

Уся комбінаторика виводиться з двох правил. Якщо їх зрозуміти, решту формул можна отримати самостійно.

Правило суми. Якщо об'єкт \(A\) можна вибрати \(m\) способами, а об'єкт \(B\) — \(n\) способами, і ці вибори взаємно виключають один одного, то вибрати «\(A\) або \(B\)» можна \(m + n\) способами.

Правило добутку. Якщо об'єкт \(A\) можна вибрати \(m\) способами, а після цього об'єкт \(B\) — \(n\) способами, то пару «\(A\) і \(B\)» можна вибрати \(m \cdot n\) способами.

Ключове слово-маркер: «або» — додаємо, «і» — множимо. Правило добутку природно поширюється на будь-яку кількість кроків: якщо дію виконують у \(k\) етапів і на \(i\)-му етапі є \(n_i\) варіантів, то всього способів \(n_1 \cdot n_2 \cdot \ldots \cdot n_k\).

Наприклад, у їдальні 3 салати, 4 перші страви й 5 десертів. Обід із трьох позицій можна скласти \(3 \cdot 4 \cdot 5 = 60\) способами — це чистий добуток, бо треба взяти салат і суп і десерт.

Факторіал і чому \(0! = 1\)

Означення. Факторіалом натурального числа \(n\) називають добуток усіх натуральних чисел від 1 до \(n\): \(n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n\). Окремо домовляються, що \(0! = 1\).

Факторіал росте дуже швидко: \(1! = 1\), \(2! = 2\), \(3! = 6\), \(4! = 24\), \(5! = 120\), \(6! = 720\), а вже \(10! = 3\,628\,800\).

Головна робоча властивість — рекурентна: \(n! = n \cdot (n-1)!\). Саме вона й пояснює рівність \(0! = 1\). Підставимо \(n = 1\):

\[ 1! = 1 \cdot 0! \quad \Longrightarrow \quad 1 = 1 \cdot 0! \quad \Longrightarrow \quad 0! = 1 \]

Тобто \(0! = 1\) — не примха й не «домовленість заради краси», а єдине значення, за якого рекурентна формула не ламається на одиниці. Є й змістовне пояснення: \(n!\) — це кількість способів упорядкувати \(n\) предметів. Порожню множину можна впорядкувати рівно одним способом — не взявши нічого. Тому \(0! = 1\).

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

\[ \frac{10!}{7!} = \frac{10 \cdot 9 \cdot 8 \cdot 7!}{7!} = 10 \cdot 9 \cdot 8 = 720 \]

Перестановки

Перестановки з \(n\) елементів — це впорядковані набори, до яких входять усі \(n\) елементів і які відрізняються лише порядком. Їх кількість \(P_n = n!\).

Чому саме \(n!\)? Правило добутку: на перше місце можна поставити будь-який із \(n\) елементів, на друге — будь-який із \(n-1\), що лишилися, далі \(n-2\), і так до останнього місця, де вибору вже немає. Отже, \(P_n = n(n-1)(n-2)\cdot\ldots\cdot 1 = n!\).

Перестановки — це «розсадити всіх», «розставити всі книжки», «скласти розклад з усіх уроків». Нічого не відкидаємо, нічого не залишаємо поза набором.

Розміщення

Розміщення з \(n\) елементів по \(k\) — це впорядковані набори по \(k\) різних елементів, узятих із \(n\) наявних. Їх кількість \[ A_n^k = \frac{n!}{(n-k)!} = n(n-1)(n-2)\cdot\ldots\cdot(n-k+1) \] (рівно \(k\) множників, кожен наступний на одиницю менший).

Виведення те саме: перше місце — \(n\) варіантів, друге — \(n-1\), і так \(k\) разів. Зверніть увагу на окремий випадок: при \(k = n\) отримуємо \(A_n^n = \dfrac{n!}{0!} = n!\) — тобто перестановки є частковим випадком розміщень. Ось тут і працює домовленість \(0! = 1\): без неї формула розміщень при \(k = n\) просто не мала б сенсу.

Розміщення — це «призові місця», «посади в комітеті», «різні за роллю позиції»: набір той самий, але хто саме перший, а хто другий — важливо.

Комбінації

Комбінації з \(n\) елементів по \(k\) — це підмножини з \(k\) різних елементів, узятих із \(n\) наявних, без урахування порядку. Їх кількість \[ C_n^k = \frac{n!}{k!\,(n-k)!} = \frac{A_n^k}{k!} \]

Друга форма запису пояснює формулу найкраще. Візьмемо всі розміщення \(A_n^k\). Кожна конкретна група з \(k\) елементів порахована в них стільки разів, скількома способами цю групу можна впорядкувати, тобто \(k!\) разів. Ділимо на \(k!\) — і кожна група лишається порахованою рівно один раз.

Комбінації — це «вибрати команду», «вибрати чергових», «вибрати букет із квітів»: усі обрані рівноправні, порядок нічого не змінює.

Як обрати формулу: алгоритм-питальник

Це ядро всієї теми. Формули ви вивчите за десять хвилин, а плутатиметеся в них роками — якщо не мати чіткого критерію. Критерій складається з двох питань, які треба ставити саме в такому порядку.

Питання 1. Чи всі \(n\) елементів входять у набір, чи ми беремо лише частину (\(k < n\))?
Питання 2. Чи змінює справу порядок елементів у наборі?

Відповіді дають відповідь:

• Беремо всі \(n\) елементів, порядок важливий → перестановки, \(P_n = n!\).
• Беремо частину (\(k\) з \(n\)), порядок важливий → розміщення, \(A_n^k\).
• Беремо частину (\(k\) з \(n\)), порядок не важливий → комбінації, \(C_n^k\).

Четвертої клітинки — «усі елементи, порядок не важливий» — не існує: узяти всі елементи без урахування порядку можна рівно одним способом. Формально це узгоджено: \(C_n^n = 1\).

Найскладніше — друге питання. Ось надійний спосіб його перевірити, не покладаючись на інтуїцію.

Тест на порядок. Візьміть два конкретні набори з тих самих елементів, записані в різному порядку. Спитайте себе: це два різні результати чи один і той самий? Різні — порядок важливий (розміщення). Один і той самий — порядок не важливий (комбінації).

Приклад роботи тесту. Із класу обирають старосту й заступника. Набори «Аня — староста, Богдан — заступник» і «Богдан — староста, Аня — заступник» — це очевидно різні результати. Порядок важливий, отже, розміщення. Тепер із того самого класу обирають двох чергових. «Аня і Богдан» та «Богдан і Аня» — це одна й та сама пара чергових. Порядок не важливий, отже, комбінації.

Ще одна підказка з тексту задачі. Слова «місце», «посада», «поспіль», «шифр», «номер», «розклад», «розставити», «розсадити» майже завжди означають порядок. Слова «група», «команда», «підмножина», «набір», «вибрати кількох» — майже завжди означають його відсутність. Але слова — лише підказка; вирішує тест.

І окреме застереження: усі три формули діють, лише коли елементи не повторюються. Якщо в задачі можна брати той самий елемент двічі (цифри в коді, кольори в прапорці), формули не працюють — там прямо застосовують правило добутку, і відповідь має вигляд \(n^k\).

Властивості комбінацій і трикутник Паскаля

Комбінації мають кілька властивостей, які помітно скорочують обчислення.

\[ C_n^k = C_n^{n-k}, \qquad C_n^0 = C_n^n = 1, \qquad C_n^1 = n \]

Перша — властивість симетрії, і вона очевидна змістовно: обрати \(k\) елементів «у команду» — це те саме, що обрати \(n-k\) елементів, які лишаються поза командою. Кожному вибору відповідає рівно один «антивибір». Перевіримо на числах: \(C_{10}^{3} = 120\) і \(C_{10}^{7} = 120\). Практична користь: якщо \(k\) більше за половину \(n\), рахуйте \(C_n^{n-k}\) — множників буде менше.

Друга ключова властивість — тотожність Паскаля:

\[ C_n^k = C_{n-1}^{k-1} + C_{n-1}^{k} \]

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

• \(n=0\): \(1\)
• \(n=1\): \(1\quad 1\)
• \(n=2\): \(1\quad 2\quad 1\)
• \(n=3\): \(1\quad 3\quad 3\quad 1\)
• \(n=4\): \(1\quad 4\quad 6\quad 4\quad 1\)
• \(n=5\): \(1\quad 5\quad 10\quad 10\quad 5\quad 1\)
• \(n=6\): \(1\quad 6\quad 15\quad 20\quad 15\quad 6\quad 1\)

Рядок з номером \(n\) — це всі числа \(C_n^0, C_n^1, \ldots, C_n^n\). Симетрія рядків — це і є властивість \(C_n^k = C_n^{n-k}\). А сума чисел рядка дорівнює \(2^n\): для \(n = 5\) маємо \(1+5+10+10+5+1 = 32 = 2^5\) — див. степінь з натуральним показником.

Зв'язок з біномом Ньютона

Числа \(C_n^k\) називають ще біноміальними коефіцієнтами, бо саме вони стоять у розкладі степеня двочлена.

\[ (a+b)^n = C_n^0 a^n + C_n^1 a^{n-1}b + C_n^2 a^{n-2}b^2 + \ldots + C_n^n b^n \]

Причина комбінаторна: розкриваючи \(n\) однакових дужок, доданок з \(b^k\) утворюється щоразу, коли ми обираємо \(b\) рівно з \(k\) дужок із \(n\). Кількість таких виборів — \(C_n^k\).

Перевірка на \(n=5\): коефіцієнти \(1, 5, 10, 10, 5, 1\) — це рівно шостий рядок трикутника Паскаля, і \((a+b)^5 = a^5 + 5a^4b + 10a^3b^2 + 10a^2b^3 + 5ab^4 + b^5\). Так само \(C_6^2 = 15\) — це коефіцієнт при \(a^4b^2\) у розкладі \((a+b)^6\).

Приклади

Приклад 1 (правила суми й добутку). З міста A до міста B ведуть 3 дороги, з B до C — 4 дороги. Крім того, є 2 прямі рейси з A до C. Скількома способами можна дістатися з A до C?

Два взаємно виключні варіанти: через B або прямим рейсом. Маршрут через B — це «дорога A–B і дорога B–C», тобто добуток: \(3 \cdot 4 = 12\). Прямих рейсів 2. За правилом суми: \(12 + 2 = 14\).

Відповідь: 14 способів.

Приклад 2 (порядок є, з повторами і без). Скільки трицифрових чисел можна скласти з цифр 1, 2, 3, 4, 5, якщо: а) цифри можуть повторюватися; б) цифри мають бути різними?

а) Повтори дозволені — жодна формула не потрібна, працює правило добутку: на кожен із трьох розрядів є 5 варіантів, разом \(5 \cdot 5 \cdot 5 = 5^3 = 125\).

б) Повторів немає, беремо 3 цифри з 5, порядок важливий (числа 123 і 321 різні) — розміщення:

\[ A_5^3 = \frac{5!}{(5-3)!} = \frac{120}{2} = 5 \cdot 4 \cdot 3 = 60 \]

Відповідь: а) 125; б) 60.

Приклад 3 (перестановки з обмеженням). На полицю ставлять 6 різних книжок. Скількома способами це можна зробити так, щоб дві конкретні книжки не стояли поруч?

Усього розставлянь: \(P_6 = 6! = 720\). Порахуємо «погані» — ті, де книжки стоять поруч. Склеїмо дві книжки в один блок: тоді переставляємо 5 об'єктів, це \(P_5 = 5! = 120\) способів, і всередині блоку книжки можна поміняти місцями \(2! = 2\) способами. «Поганих» розставлянь \(120 \cdot 2 = 240\). Шукана кількість: \(720 - 240 = 480\).

Відповідь: 480 способів.

Приклад 4 (розміщення). У змаганні беруть участь 10 спортсменів. Скількома способами можуть розподілитися золота, срібна й бронзова медалі?

Тест на порядок: «Петро — золото, Іван — срібло» і «Іван — золото, Петро — срібло» — різні результати. Порядок важливий, беремо 3 з 10 — розміщення:

\[ A_{10}^{3} = \frac{10!}{7!} = 10 \cdot 9 \cdot 8 = 720 \]

Відповідь: 720 способів.

Приклад 5 (комбінації). У класі 25 учнів. Скількома способами можна обрати 4 чергових?

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

\[ C_{25}^{4} = \frac{25!}{4!\,21!} = \frac{25 \cdot 24 \cdot 23 \cdot 22}{1 \cdot 2 \cdot 3 \cdot 4} = \frac{303\,600}{24} = 12\,650 \]

Відповідь: 12 650 способів.

Приклад 6 (комбінований вибір). У гуртку 7 хлопців і 5 дівчат. Скількома способами можна скласти команду з 3 хлопців і 2 дівчат?

Усередині кожної групи порядок не важливий, тому двічі рахуємо комбінації, а результати перемножуємо (треба обрати хлопців і дівчат):

\[ C_7^3 = \frac{7 \cdot 6 \cdot 5}{1 \cdot 2 \cdot 3} = 35, \qquad C_5^2 = \frac{5 \cdot 4}{1 \cdot 2} = 10 \] \[ N = C_7^3 \cdot C_5^2 = 35 \cdot 10 = 350 \]

Відповідь: 350 способів.

Приклад 7 (біном Ньютона). Знайти коефіцієнт при \(x^5\) у розкладі \((x+2)^8\).

У формулі бінома \(a = x\), \(b = 2\), \(n = 8\). Доданок з \(x^5\) відповідає \(a^5 b^3\), тобто \(k = 3\):

\[ C_8^3 \cdot x^5 \cdot 2^3 = \frac{8 \cdot 7 \cdot 6}{1 \cdot 2 \cdot 3} \cdot x^5 \cdot 8 = 56 \cdot 8 \cdot x^5 = 448 x^5 \]

Відповідь: 448.

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

• Плутають розміщення й комбінації. Найчастіша помилка теми: беруть \(A_n^k\) там, де потрібні \(C_n^k\), і отримують відповідь, більшу рівно в \(k!\) разів. Лікується тестом на порядок — двома конкретними наборами, а не відчуттям.
• Додають замість множення (і навпаки). «Або» — сума, «і» — добуток. Якщо етапи виконуються послідовно й обидва обов'язкові, це завжди добуток.
• Застосовують формули там, де є повтори. Якщо елемент можна взяти двічі (цифри в PIN-коді, кидки кубика), \(A_n^k\) і \(C_n^k\) не діють — працює правило добутку \(n^k\).
• Вважають, що \(0! = 0\). Це руйнує всі формули з \((n-k)!\) при \(k = n\): виникає ділення на нуль. За означенням \(0! = 1\).
• Скорочують факторіали «в лоб». Обчислювати \(25!\) не треба й неможливо в умі. Скорочуйте одразу: \(\dfrac{25!}{21!} = 25 \cdot 24 \cdot 23 \cdot 22\).
• Забувають про обмеження в умові. «Не поруч», «обов'язково включити X», «перша цифра не нуль» — такі умови рахують або через доповнення (усе мінус погані), або фіксуючи потрібні елементи. Ігнорування обмеження дає завищену відповідь.
• Множать усе підряд у комбінованих задачах. У прикладі 6 групи хлопців і дівчат незалежні, тому добуток правильний. Але якщо групи перетинаються або умова «рівно 3» замінена на «не менше 3», задачу треба розбити на випадки й додати результати.

Висновок

Комбінаторика тримається на двох правилах (сума й добуток) і трьох формулах (\(P_n\), \(A_n^k\), \(C_n^k\)). Формули виводяться з правил, а не запам'ятовуються окремо. Головна навичка теми — не рахувати факторіали, а правильно ставити два питання: чи всі елементи беремо і чи важливий порядок. Хто відповідає на них упевнено, той розв'язує комбінаторні задачі НМТ швидше, ніж читає умову. Далі ці ж числа знадобляться в темах про ймовірність і біном Ньютона, а звички акуратного скорочення дробів — усюди, від НСД і НСК до алгебри старшої школи.

Якщо після цієї статті ви все ще вагаєтеся між \(A_n^k\) і \(C_n^k\) у конкретній задачі — це нормально, критерій відпрацьовується на задачах, а не на теорії. Запишіться на пробне заняття в Tutor-Math: розберемо ваш тип задач і доведемо вибір формули до автоматизму.

Чим розміщення відрізняються від комбінацій?

Тільки врахуванням порядку. Розміщення \(A_n^k\) вважають набори з різним порядком різними результатами, комбінації \(C_n^k\) — однаковими. Тому \(A_n^k = C_n^k \cdot k!\): кожну комбінацію можна впорядкувати \(k!\) способами. Наприклад, обрати 3 призери з 10 — це \(A_{10}^{3} = 720\), а обрати 3 учасників у команду з 10 — це \(C_{10}^{3} = 120\), рівно в \(3! = 6\) разів менше.

Чому \(0! = 1\), а не 0?

Через рекурентну властивість \(n! = n \cdot (n-1)!\). При \(n = 1\) вона дає \(1! = 1 \cdot 0!\), тобто \(0! = 1\). Змістовно: \(n!\) — кількість способів упорядкувати \(n\) предметів, а порожній набір упорядковується рівно одним способом. Якби \(0!\) дорівнював нулю, формули \(A_n^n = \frac{n!}{0!}\) і \(C_n^0 = \frac{n!}{0!\,n!}\) давали б ділення на нуль.

Як швидко зрозуміти, чи важливий порядок у задачі?

Візьміть два конкретні набори з тих самих елементів у різному порядку й спитайте: це різні результати чи один і той самий? «Староста Аня, заступник Богдан» і «староста Богдан, заступник Аня» — різні, отже, розміщення. «Чергові Аня і Богдан» та «чергові Богдан і Аня» — одне й те саме, отже, комбінації. Слова «місце», «посада», «шифр» зазвичай означають порядок; «команда», «група», «набір» — його відсутність.

Що робити, якщо елементи можуть повторюватися?

Формули \(P_n\), \(A_n^k\), \(C_n^k\) розраховані на різні елементи й не працюють. Для наборів з повторами застосовують безпосередньо правило добутку: якщо на кожній із \(k\) позицій є \(n\) варіантів, кількість наборів дорівнює \(n^k\). Наприклад, чотиризначних PIN-кодів із цифр 0–9 існує \(10^4 = 10\,000\).