Основні правила комбінаторики. Перестановки

Скількома способами учні вашого класу можуть стати один за одним у черзі до буфету? Скількома способами можна вибрати у вашому класі старосту та його заступника? Скількома способами можуть бути розподілені золоті, срібні та бронзові медалі на чемпіонаті світу з футболу?

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

В основі розв’язування більшості комбінаторних задач лежать два правила: правило суми та правило добутку.

Правило суми

📐Означення — Правило суми

Якщо множини $A$ і $B$ такі, що $n(A) = m$ , $n(B) = k$ , $A \cap B = \varnothing$ , то вибір « $a$ або $b$ », де $a \in A$ , $b \in B$ , можна здійснити $m + k$ способами.

Це правило можна проілюструвати за допомогою відомої властивості: якщо множини $A$ і $B$ є скінченними, причому $A \cap B = \varnothing$ , то $n(A \cup B) = n(A) + n(B)$ .

Правило суми можна узагальнити. Якщо множини $A_1, A_2, \ldots, A_m$ попарно не перетинаються і такі, що $n(A_1) = k_1$ , $n(A_2) = k_2$ , …, $n(A_m) = k_m$ , то вибір « $a_1$ , або $a_2$ , або …, або $a_m$ », де $a_1 \in A_1$ , $a_2 \in A_2$ , …, $a_m \in A_m$ , можна здійснити $k_1 + k_2 + \ldots + k_m$ способами.

✎Приклад — Туристичні маршрути

Умова. Туриста зацікавили 5 маршрутів по Наддніпрянщині та 7 маршрутів по Карпатах. Скількома способами він може організувати свою відпустку, маючи час лише на один маршрут?

Розв’язання. Оскільки всього є $5 + 7 = 12$ різних маршрутів, то один із них можна вибрати 12 способами.

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

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

📐Означення — Правило добутку

Якщо елемент $a$ можна вибрати $m$ способами і після кожного такого вибору елемент $b$ можна вибрати $k$ способами, то вибір « $a$ і $b$ » у вказаному порядку, тобто вибір упорядкованої пари $(a; b)$ , можна здійснити $mk$ способами.

Правило добутку також можна природно узагальнити. Якщо елемент $a_1$ можна вибрати $k_1$ способами, елемент $a_2$ — $k_2$ способами й т. д., елемент $a_m$ — $k_m$ способами за умови дотримання принципу незалежності кількості виборів, то вибір « $a_1$ , і $a_2$ , і …, і $a_m$ », тобто вибір упорядкованого набору $(a_1; a_2; \ldots; a_m)$ , можна зробити $k_1 \cdot k_2 \cdot \ldots \cdot k_m$ способами.

✎Приклад 1 — Кількість дільників

Умова. Скільки натуральних дільників має число $2^4 \cdot 5^3 \cdot 7^6$ ?

Розв’язання. Будь-який дільник даного числа має вигляд $2^{k_1} \cdot 5^{k_2} \cdot 7^{k_3}$ , де $k_1, k_2, k_3$ — цілі числа, які задовольняють умови $0 \leqslant k_1 \leqslant 4$ , $0 \leqslant k_2 \leqslant 3$ , $0 \leqslant k_3 \leqslant 6$ .

Число $k_1$ можна вибрати 5 способами, число $k_2$ — 4 способами, число $k_3$ — 7 способами. Отже, за узагальненим правилом добутку зазначений набір можна вибрати $5 \cdot 4 \cdot 7 = 140$ способами.

Відповідь: 140 дільників.

Упорядкована множина

📐Означення — Упорядкована множина

Множину $M$ , яка складається з $n$ елементів ( $n \in \mathbb{N}$ ), називають упорядкованою, якщо між нею та множиною, яка складається з перших $n$ натуральних чисел, установлено взаємно однозначну відповідність.

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

📐Означення — Перестановка

Перестановкою скінченної множини $M$ називають будь-яку упорядковану множину, утворену з усіх елементів множини $M$ .

Наприклад, існує 6 перестановок множини $M = \{a, b, c\}$ :

$(a; b; c)$ , $(a; c; b)$ , $(b; a; c)$ , $(b; c; a)$ , $(c; a; b)$ , $(c; b; a)$ .

Перестановки заданої скінченної множини різняться лише порядком слідування елементів.

Кількість перестановок $n$ -елементної множини $M$ позначають символом $P_n$ , використовуючи першу літеру французького слова permutation — перестановка.

⚡Теорема — Кількість перестановок

Для будь-якого натурального $n$ справедлива формула

P_n = n!

де $n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n$ (читають: « $n$ факторіал»). За означенням вважають, що $0! = 1$ і $1! = 1$ .

Доведення. Нехай множина $M$ складається з $n$ елементів. Записати будь-яку перестановку множини $M$ — це фактично надати кожному елементу певний номер від 1 до $n$ . Виберемо елемент $a$ із множини. Існує $n$ способів присвоїти йому номер. Далі виберемо елемент $b$ . Оскільки один номер уже присвоєно, то існує $n - 1$ спосіб. Продовжуючи ці міркування, для останнього невибраного елемента існує лише один спосіб. Отже, за узагальненим правилом добутку:

P_n = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1 = n!

✎Приклад 2 — Вісім тур на шахівниці

Умова. Скількома способами можна розташувати на шаховій дошці 8 тур так, щоб вони не били одна одну?

Розв’язання. Для того щоб тури не могли бити одна одну, на кожній горизонталі та на кожній вертикалі має стояти тільки одна тура. Нехай $a_1$ — номер вертикалі, на якій стоїть тура з першої горизонталі, $a_2$ — номер вертикалі з другої горизонталі, …, $a_8$ — номер вертикалі з восьмої горизонталі.

Тоді $(a_1; a_2; \ldots; a_8)$ — деяка перестановка множини $\{1, 2, \ldots, 8\}$ . Кожній такій перестановці відповідає деяке розташування тур.

Отже, шукана кількість способів дорівнює $P_8 = 8! = 40\,320$ .

Відповідь: $8! = 40\,320$ .

✏Вправа — Задачі на перестановки

Скількома способами можна розставити на полиці 7 різних книг?
Скількома способами можуть сісти в автомобіль 5 чоловік, якщо кожний із них може бути водієм?
У школі 20 класів і 20 класних керівників. Скількома способами можна розподілити класне керівництво між учителями?
Скільки п’ятицифрових чисел можна скласти із цифр 1, 2, 3, 4, 5, причому так, щоб у кожному числі всі цифри були різними?