Комбінації

Комбінації використовуємо тоді, коли з певної множини об'єктів вибираємо певну кількість об'єктів і при цьому не важливо, в якому порядку ми їх вибираємо. Типова задача — лотерея «6 із 49»: в урні маємо 49 номерів і витягуємо з них 6, причому байдуже, в якому порядку їх витягнуто.

Виведення формули

Нехай маємо якусь множину M, наприклад M = {a, b, c, d, e}. Тоді комбінація з n по k (k-елементна комбінація) — це підмножина K ⊆ M, що містить рівно k елементів. Оскільки K — множина, то порядок, звісно, не важливий. Отже, триелементною комбінацією з множини M може бути {a, b, d} або {b, c, d}.

Відмінність від розміщень у тому, що для розміщень порядок був важливим, тому (a; b; e) і (e; b; a) — різні розміщення, але це однакові комбінації, адже (a; b; e) і (e; b; a) містять однакові елементи; те, що вони йдуть в іншому порядку, для комбінацій нас не цікавить.

Проте розміщення можна використати, щоб отримати формулу для кількості всіх різних комбінацій. Ми знаємо, що розміщень з n елементів по k є рівно

$$ A_n^k = \frac{n!}{(n-k)!}. $$

Якби ми рахували кількість усіх триелементних розміщень із попередньої множини M = {a, b, c, d, e}, то отримали б A₅³ = 60 різних розміщень. Однак для кожної трійки в цьому наборі були б і всі її перестановки. Тобто була б трійка abc, а також трійки acb, bac, bca, cab і cba. Це шість різних розміщень, але одна комбінація, бо всі вони мають однакові елементи.

Отже, якщо маємо якусь трійку, скільки різних перестановок цієї трійки існує? Рівно 3!. Іншими словами, триелементних розміщень рівно в 3! разів більше, ніж триелементних комбінацій. Замість однієї комбінації ми рахуємо 3! розміщень, тобто кожну перестановку цієї трійки. Тому якщо кількість розміщень поділити на 3!, отримаємо кількість комбінацій.

Попередні міркування можна узагальнити: якщо шукаємо кількість усіх різних комбінацій з n елементів по k, то ця кількість, позначимо її C_n^k, дорівнює

$$ C_n^k = \frac{A_n^k}{k!}, $$

тобто кількість розміщень, поділена на k!, що є кількістю перестановок кожного набору з k елементів. Формулу можна спростити, розписавши формулу для обчислення розміщень:

$$ C_n^k = \frac{A_n^k}{k!} = \frac{n!}{(n-k)!}\cdot\frac{1}{k!} = \frac{n!}{(n-k)!\cdot k!}. $$

Приклад: кількість двоелементних комбінацій з множини {a, b, c} дорівнює

$$ C_3^2 = \frac{3!}{1!\cdot2!} = 3 $$

і це такі комбінації: {a, b}, {a, c} і {b, c}. Для триелементних комбінацій із початкової множини M = {a, b, c, d, e} отримали б кількість

$$ C_5^3 = \frac{5!}{(5-3)!\cdot3!}=10 $$

і це такі комбінації: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

Біноміальний коефіцієнт

Кількість комбінацій C_n^k називають також біноміальним коефіцієнтом, і його часто записують у такому вигляді:

$$ {n \choose k} $$

Це ніби дріб без дробової риски (яку ти все одно за звичкою писатимеш), але з дужками (а от вони обов'язкові, без них не можна). Читаємо його так: «біноміальний коефіцієнт з n по k». Значення біноміального коефіцієнта таке саме, як C_n^k.

$$ C_n^k = {n \choose k} = \frac{n!}{(n-k)!\cdot k!} $$

Тож якщо маємо множину з 5 елементів і вибираємо з неї четвірки, то їхня загальна кількість дорівнюватиме

$$ {5 \choose 4} = \frac{5!}{1! \cdot 4!} = 5. $$

Основні співвідношення

Для біноміального коефіцієнта і n ∈ ℕ₀ виконується:

$$\begin{eqnarray} {n \choose 0} = {n \choose n} = {0 \choose 0} &=& 1\\ {n \choose 1} &=& n \end{eqnarray}$$

Далі для n, k ∈ ℕ₀ і k ≤ n виконується

$$\begin{eqnarray} {n \choose n - k} &=& {n \choose k}. \end{eqnarray}$$

А для n, k ∈ ℕ₀ і k < n виконується

$$\begin{eqnarray} {n \choose k} + {n \choose k+1} &=& {n+1 \choose k+1}. \end{eqnarray}$$

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

1. Почнімо з уже згаданої лотереї. У ній з урни, де 49 кульок, витягують 6 кульок. Скільки різних результатів може бути?

   Насамперед: чи важливий порядок витягування номерів? Не важливий, ми вгадуємо лише номери, а не їхній порядок. Використаємо комбінації. Маємо 49 кульок, витягуємо 6 кульок, отримуємо біноміальний коефіцієнт

   $$ {49 \choose 6} = \frac{49!}{(49-6)!\cdot6!}=\frac{49!}{43!\cdot6!} = 13{,}983,816 $$

   Існує всього 13 983 816 можливих результатів розіграшу. Що, до речі, дає нам ймовірність виграшу при одній ставці 1/13,983,816, а це 0{,}00000715112 %.

2. Максим на сільській вечірці з танцями, де є 13 гарних дівчат, з якими йому хотілося б потанцювати. Максим знає, що за вечір зможе потанцювати з 4 різними дівчатами. Зі скількох різних четвірок він може вибирати?

   Це знову простий приклад на комбінації, порядок не важливий, Максимові однаково буде добре і з першою дівчиною, і з останньою. Отже, маємо множину з 13 дівчат, з яких вибираємо щоразу 4. Це веде до біноміального коефіцієнта

   $$ {13 \choose 4} = 715. $$

3. Маємо групу з п'ятдесяти людей — половина чоловіків і половина жінок. Скільки існує різних трійок людей, якщо вони не повинні складатися лише з однієї статі (тобто в трійці не можуть бути три чоловіки або три жінки)?

   Це вже трохи складніша комбінація. Якщо виключити трійки людей однієї статі, залишаться лише дві можливості складу трійки — двоє чоловіків і одна жінка або один чоловік і дві жінки, причому кількість комбінацій першої групи (двоє чоловіків і одна жінка) така сама, як кількість комбінацій другої групи. Тому досить обчислити кількість комбінацій першої групи й помножити її на два. Тепер це знову легко. Визначимо кількість комбінацій різних пар чоловіків — це двадцять п'ять по два — і помножимо її на кількість комбінацій однієї жінки (це двадцять п'ять, див. основні співвідношення вище, а саме другий рядок). Цей результат залишилося лише помножити на два, і маємо остаточний результат.

   $$ 2 \cdot {25 \choose 2} \cdot {25 \choose 1} = 15000. $$

4. У коробці 15 виробів, з яких 4 браковані. Скількома способами можна вибрати 6 виробів так, щоб

   • жоден не був бракованим? Зараз вибираємо 6 виробів з 15 − 4 = 11 виробів, які не браковані. Отже, отримуємо біноміальний коефіцієнт

     $$ {11 \choose 6} = 462. $$

   • був бракованим рівно один виріб? Вибираємо множину, що містить 5 справних виробів і 1 бракований. Справних виробів маємо разом 11, бракованих — 4. Застосуємо комбінаторне правило добутку й отримаємо результат:

     $$ {11 \choose 5} \cdot {4 \choose 1} = 1848 $$

   • був бракованим щонайбільше один виріб? Для розв'язання скористаємося попередніми результатами. Знаємо, що є 462 можливості вибрати рівно 6 справних виробів і є 1848 можливостей вибрати п'ять справних і один бракований виріб. Тож застосуємо комбінаторне правило суми, додамо ці результати й отримаємо шуканий результат, тобто щонайбільше один бракований виріб (= або жодного бракованого, або рівно один). Результат такий: 462 + 1848 = 2310.