Комбінаторика

Потрібно дізнатися, скільки різних п'ятірок карт можна вибрати з колоди в 32 карти? Саме такі задачі розв'язує комбінаторика. Існують два основні комбінаторні правила — суми та добутку. Усі інші методи є лише розширенням цих основних принципів.

Комбінаторне правило суми

Правило суми дуже просте: якщо множини A, B не мають жодного спільного елемента, то кількість усіх способів вибрати один елемент з об'єднання A ∪ B дорівнює |A| + |B|, тобто сумі кількостей елементів цих множин.

Почнімо з легкого прикладу. Маємо 6 червоних і 8 синіх кульок. Висипаємо їх в одну урну. Скільки всього є можливостей, якщо ми витягуємо одну кульку? Спочатку ми мали множину червоних кульок, позначимо її A, і множину синіх кульок, позначимо її B. Ці множини не перетинаються, тобто не мають жодної спільної кульки. Ми хочемо витягти одну кульку, тож усього є |A| + |B| = 6 + 8 = 14 можливостей. Ось і все.

Комбінаторне правило добутку

Знову маємо дві множини, Ж і Ч. Множина Ж містить трьох жінок, а множина Ч — чотирьох чоловіків. Тепер запитаємо: скільки різних пар «чоловік — жінка» можна утворити з цих множин? Що ми робимо: беремо одну жінку й добираємо до неї якогось чоловіка. Кількість усіх пар підрахуємо так: візьмемо одну жінку, Катю, і по черзі поставимо поруч із нею всіх чоловіків. Отримаємо 4 різні пари, адже до неї можна дібрати чотирьох різних чоловіків. Те саме зробимо для решти двох жінок, і кожна утворить ще по 4 пари. Ось і все, разом маємо 4 + 4 + 4 = 12 пар.

Що ми насправді зробили? Помножили кількості елементів обох множин. Було 3 жінки й 4 чоловіки, тож загальна кількість пар дорівнює 3 · 4 = 12. Звідси назва: комбінаторне правило добутку. Якщо ми складаємо пари з елементів двох множин, достатньо просто помножити кількість елементів однієї множини на кількість елементів другої.

Переконатися, що це справді так, можна нижче. Ось усі пари, які можна утворити з 3 жінок і 4 чоловіків. Кожен рядок відповідає можливостям для однієї з жінок, а кожен стовпець — можливостям для одного з чоловіків. Отже, маємо три рядки й чотири стовпці, разом $\text{рядки} \cdot \text{стовпці}$ можливостей.

$$\begin{eqnarray} &&(Ж_1; Ч_1), (Ж_1; Ч_2), (Ж_1; Ч_3), (Ж_1; Ч_4), \\ &&(Ж_2; Ч_1), (Ж_2; Ч_2), (Ж_2; Ч_3), (Ж_2; Ч_4), \\ &&(Ж_3; Ч_1), (Ж_3; Ч_2), (Ж_3; Ч_3), (Ж_3; Ч_4) \end{eqnarray}$$

Розв'язані приклади

1. Скільки існує різних двоцифрових чисел? Який вигляд має таке двоцифрове число? На першому місці стоїть одна з цифр 1, …, 9, а на другому місці може стояти ще й нуль: 0, …, 9. Отже, у першій множині маємо 9 цифр, у другій — 10. Застосуємо комбінаторне правило добутку й отримаємо остаточний результат: 9 · 10 = 90.

• Скільки існує різних трицифрових чисел, у яких жодна цифра не повторюється? На першому місці знову може стояти дев'ять цифр, бо число не може починатися з нуля. На другому місці можуть бути всі цифри, зокрема нуль, але не цифра, що стоїть на першому місці, тому від десяти можливих цифр віднімаємо одиницю (наприклад, якщо наше трицифрове число починається з четвірки, зрозуміло, що на другому місці четвірки вже бути не може, бо вона зустрічалася б у числі двічі). На третьому місці знову можуть бути всі цифри, але не ті, що стоять на першому або другому місці. Причина та сама. Якщо на першому місці цифра 4, а на другому цифра 7, то на третє місце можна поставити одну цифру з {0, …, 9} ∖ {4, 7}. Від загальної кількості десяти цифр потрібно відняти двійку. Тепер залишилося перемножити: 9 · 9 · 8 = 648. Отже, усього існує 648 таких чисел.
• Двічі поспіль кидаємо звичайний ігровий кубик. Скільки різних результатів можна отримати? У першому кидку на кубику може випасти 6 різних результатів. У другому так само, тож загальна кількість можливостей дорівнює 6 · 6 = 36.
• Двічі поспіль кидаємо кубик. Скільки різних результатів можна отримати, якщо в першому кидку випало парне число? У першому кидку випало парне число, тобто одне з чисел 2, 4, 6, а це разом 3 можливості. У другому кидку може випасти будь-яке число, тож усього маємо 3 · 6 = 18 можливостей.