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

Означення

Комбінаторика — це розділ математики, що вивчає методи підрахунку кількості можливих варіантів вибору або розташування об'єктів у певних умовах. В основі більшості задач лежать два фундаментальні правила.

Основні правила підрахунку

Правило суми (принцип «АБО»): якщо об'єкт можна вибрати або способом $A$ (з $n$ варіантів), або способом $B$ (з $m$ варіантів), то загальна кількість способів: $n + m$ .
Правило добутку (принцип «І»): якщо вибір складається з двох послідовних кроків, де перший має $n$ варіантів, а другий — $m$ , то загальна кількість комбінацій: $n \cdot m$ .

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

Вибір формули залежить від того, чи всі елементи використовуються та чи має значення їхній порядок.

Вид вибірки	Усі елементи?	Порядок важливий?	Формула
Перестановки ( $P_{n}$ )	Так	Так	$P_{n} = n!$
Розміщення ( $A_{n}^{k}$ )	Ні	Так	$A_{n}^{k} = \frac{n !}{( n - k )!}$
Комбінації ( $C_{n}^{k}$ )	Ні	Ні	$C_{n}^{k} = \frac{n !}{k ! ( n - k )!}$

1. Перестановки ( $P_{n}$ )

Використовуються, коли ми міняємо місцями всі об'єкти.
Приклад: скількома способами 5 учнів можуть стати в ряд?
$P_{5} = 5! = 120$ .

2. Розміщення ( $A_{n}^{k}$ )

Вибираємо частину елементів, і їхній порядок (ролі) важливий.
Приклад: з 25 учнів обрати старосту та заступника.
$A_{25}^{2} = \frac{25 !}{( 25 - 2 )!} = 24 \cdot 25 = 600$ .

3. Комбінації ( $C_{n}^{k}$ )

Вибираємо частину елементів, але порядок не має значення.
Приклад: з 25 учнів обрати двох для чергування.
$C_{25}^{2} = \frac{25 !}{2 ! ( 25 - 2 )!} = 300$ .

Що таке факторіал?

Факторіал числа $n$ (позначається $n!$ ) — це добуток усіх натуральних чисел від 1 до $n$ .

$5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$
Важливо: за домовленістю $0! = 1$ .