Перестановки й комбінації: пояснення

Правило добутку

Комбінаторні задачі питають, скількома способами може щось статися. Основа — правило добутку: якщо один вибір можна зробити $m$ способами, а другий, незалежний, — $n$ способами, то обидва разом можна зробити $m \times n$ способами. Ідея працює для будь-якої кількості етапів.

Маючи 3 сорочки, 4 пари штанів і 2 пари взуття, можна скласти $3 \times 4 \times 2 = 24$ різні комплекти. Чотиризначний ПІН-код із цифр від 0 до 9 з дозволеними повтореннями має $10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000$ варіантів. Усі формули цієї статті — скорочення такого множення: якщо задача здається дивною, повернення до поетапного підрахунку завжди надійне.

Факторіали

Щоб поставити $n$ різних предметів у ряд, є $n$ варіантів для першого місця, $n - 1$ для другого й так далі до 1. Цей добуток називають факторіалом $n$:

Так, $5! = 120$: п'ять книжок можна розставити на полиці 120 різними способами. За означенням $0! = 1$, що зберігає узгодженість формул нижче: є рівно один спосіб упорядкувати «нічого». Факторіали ростуть запаморочливо швидко: $10! = 3{,}628{,}800$, а перетасована колода карт має $52!$ можливих порядків — це число з 68 цифр.

Перестановки й розміщення: порядок важливий

Розміщення — це впорядкована послідовність із $r$ предметів, вибраних із $n$ різних предметів. Оскільки порядок важливий, «перший — другий — третій» відрізняється від «третій — другий — перший». Кількість розміщень дорівнює

Розсаджування людей за круглим столом — окремий випадок. Якщо кожен пересяде на один стілець далі, вийде те саме розсаджування, тому $n$ осіб можна розсадити $(n-1)!$ різними способами. Шість осіб за круглим столом мають $5! = 120$ розсаджувань, а не 720. Це називають коловою перестановкою.

Комбінації: порядок не важливий

Комбінація — це вибірка, у якій важливо лише те, які елементи вибрано. Якщо вибрати до комісії Анну, Бориса й Клару, вийде та сама комісія, хоч у якому порядку їх вибирали б. Кожній групі з $r$ предметів відповідає $r!$ розміщень, тому ділимо на це число:

Комбінації симетричні: $\binom{n}{r} = \binom{n}{n-r}$, бо вибрати 3 осіб, які ввійдуть, — те саме, що вибрати 5, які залишаться поза комісією. Це також числа трикутника Паскаля й коефіцієнти розкладу бінома $(a + b)^n$.

Як зрозуміти, що потрібно

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

• Місця в змаганні, рейтинги, ПІН-коди, розсаджування й розклади: розміщення.
• Команди, комісії, карткові руки, лотерейні квитки й начинки піци: комбінації.
• Посади всередині групи, наприклад голова й скарбник, роблять порядок важливим, навіть якщо людей вибирають з однієї групи.

Швидка перевірка: кількість розміщень завжди в $r!$ разів більша за кількість комбінацій. Якщо ваші два результати не задовольняють цього співвідношення, один із них хибний.

Підрахунок із повтореннями й однаковими літерами

Якщо елементи можуть повторюватися, формули змінюються. Упорядкованих вибірок із повтореннями $n^r$, як у прикладі з ПІН-кодом. Невпорядкованих вибірок із повтореннями, наприклад 3 кульки морозива з 5 смаків, коли смаки можуть повторюватися, буде

Розставляння літер із повтореннями потребує ще однієї поправки: треба ділити на факторіал кожної кількості повторень, бо перестановка однакових літер нічого не змінює. Англійське написання назви річки Міссісіпі складається з 11 літер, серед яких 4 літери I, 4 літери S і 2 літери P: отже, воно має $\frac{11!}{4!\,4!\,2!} = 34{,}650$ різних анаграм.

Підрахунок для обчислення ймовірностей

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

Карткові ігри дають ще більше вправ. Існує $\binom{52}{5} = 2{,}598{,}960$ можливих розкладів із п'яти карт. Розклад з усіма чотирма тузами потребує лише ще однієї карти, вибраної з решти 48, тому ймовірність дорівнює $\frac{48}{2{,}598{,}960} = \frac{1}{54{,}145}$.

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

• Використовувати розміщення для команди чи комісії, що завищує підрахунок у $r!$ разів.
• Забувати, що $0! = 1$, через що ламаються формули на кшталт $\binom{n}{n}$.
• Не враховувати однакових елементів, наприклад в анаграмах з однаковими літерами.
• Перемножувати залежні етапи, не коригуючи наступних кількостей.

Калькулятор перестановок і комбінацій обчислює ${}_nP_r$ і ${}_nC_r$ з усіма кроками через факторіали, а калькулятор імовірностей перетворює ці кількості на ймовірності.

Трикутник Паскаля й підмножини

Кожне число в трикутнику Паскаля дорівнює сумі двох чисел безпосередньо над ним, а рядок $n$ містить значення $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. Рядок 4 — це 1, 4, 6, 4, 1, саме коефіцієнти $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$. Правило побудови трикутника саме є результатом підрахунку:

Щоб зрозуміти чому, зафіксуйте один елемент. Будь-яка вибірка з $r$ елементів або містить його, і тоді залишається вибрати $r - 1$ елементів з решти $n - 1$, або не містить, і тоді всі $r$ елементів вибирають з решти $n - 1$. Сума всього рядка дорівнює $2^n$ — загальній кількості підмножин множини з $n$ елементів, адже кожен елемент або входить, або ні. Тому піцерія з 8 начинками може приготувати $2^8 = 256$ різних піц, зважаючи й на піцу зовсім без начинки.

Вправи

1. Скількома способами можна поставити на полицю 4 книжки, вибрані із 7 різних? Розв'язання: ${}_7P_4 = 7 \times 6 \times 5 \times 4 = 840$.
2. Скількома способами можна вибрати 4 начинки з 10? Розв'язання: $\binom{10}{4} = 210$.
3. Скільки різних анаграм має слово АНАНАС? Розв'язання: $\frac{6!}{3!\,2!} = 60$.
4. Скільки п'ятилітерних кодів можна скласти з 26 літер, якщо повторення дозволені? Розв'язання: $26^5 = 11{,}881{,}376$.

Поширені запитання