✖

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

Kapitoly: Комбінаторика, Розміщення, Перестановки, Комбінації, Розміщення з повтореннями, Комбінації з повтореннями, Скільки існує різних PIN-кодів?

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

Формула

Повторімо самі розміщення. Нехай маємо множину цифр {1, 2, 3, 4, 5}. Скільки трицифрових чисел можна з них скласти, якщо жодна цифра не повинна повторюватися? Це типовий приклад на розміщення, який розв'язують відомою формулою

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

Скільки можна було б скласти п'ятицифрових чисел?

$$ A_5^5 = \frac{5!}{(5-5)!}=\frac{5!}{0!}=5!=120. $$

Зауважмо: якщо маємо множину з п'яти елементів і шукаємо кількість усіх різних наборів з п'яти елементів, то результат дорівнює 5!. Це можна узагальнити: якщо множина має n елементів, то існує всього n! різних наборів з n елементів. Так ми приходимо до поняття перестановки.

Що таке перестановка

Якщо маємо множину M з n елементів, то перестановка — це довільний впорядкований набір з n елементів множини M, у якому жоден елемент не повторюється. Приклад: якщо M = {a, b, c, d}, то перестановками є, наприклад, (a; b; d; c) або (d; b; a; c). Кількість усіх різних перестановок дорівнює

$$ P_n = A_n^n = n! $$

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

  1. Маєш шість книжок і хочеш поставити їх на полицю в якомусь порядку. Скільки всього існує різних порядків? Маємо шість книжок, і щоразу переставляємо всі книжки, тож результат дорівнює P6 = 6! = 720.

  2. До твоїх 6 українських книжок із попереднього прикладу додалися 4 англійські. Скількома способами можна розставити ці 10 книжок на полиці, якщо всі українські мають стояти разом і всі англійські теж разом?

    Які є варіанти розставити книжки? Можна спочатку поставити шість українських книжок, а потім чотири англійські, або навпаки — спочатку чотири англійські, а потім шість українських. При цьому існує 6! способів розставити українські книжки та 4! способів розставити англійські. Застосуємо комбінаторне правило добутку і перемножимо ці результати: 6! · 4! = 17,280. Оскільки є дві можливості розташувати групи книжок (українські, потім англійські, і навпаки), це число ще множимо на два. Остаточний результат: 17,280 · 2 = 34,560.