Перестановки з повтореннями

Формулу для кількості перестановок Р_п одержують із формули для кількості розміщень без повторень:

Приклад 8.1. Знайдемо кількість рядків, які можна утворити, переставляючи букви слова SOFTWARE. Оскільки жодна буква тут не повторюється, то можна утворити Р₈ =8!= 40320 рядків. ▲

Розглянемо складніший вид перестановок.

Означення 8.1. Нехай є n елементів k різних типів, а число n_j (j=1,…,k) — кількість елементів j- гo типу. Очевидно, що n₁+п₂+...+n_k=п. Перестановки з n елементів за такої умови називають перестановками з повтореннями. Кількість таких перестановок позначають як .

ТЕОРЕМА 8.1. Кількість різних перестановок з повтореннями рівна:

.

Доведення. Щоб знайти явний вираз для , візьмемо окрему перестановку та замінимо в ній усі однакові елементи різними. Тоді кількість різних перестановок, котрі можна отримати з узятої однієї перестановки, дорівнює . Якщо зробити це для кожної перестановки, то одержимо n! перестановок. Отже, , звідки

. ▲

Приклад 8.2. Знайдемо, скільки рядків можна утворити, переставляючи букви слова POSSESSIONLESSNESSES. У цьому слові є повторні входження букв, тому скористаємося формулою для перестановок із повтореннями:

69837768000 слів. ▲

Задача розкладання в ящики. Дано n різних предметів і k ящиків. Потрібно покласти в перший ящик n₁ предметів, у другий — n₂ предметів,…, k -й — n_k предметів, де . Тут — фіксовані числа. Скількома способами можна це зробити?

Розв’язання.

1-й спосіб. Занумеруємо всі n предметів. Кожен предмет попадає у свій ящик:

1-й предмет	2-й предмет	…	…	n -й предмет
a1 ящик	a2 ящик	…	…	an ящик

Як бачимо, кожному розподілу предметів по ящиках відповідає певна послідовність a₁a₂…a_n. Кількість всіх послідовностей відповідає кількості способів розподілу предметів.

Послідовність a₁a₂…a_n є перестановкою з повтореннями чисел { 1, 2, …, k }, бо перестановкою її елементів ми отримаємо інакший розподіл, а її елементи повторюються. Очевидно, що “1” повторюватиметься n₁ разів, “2” повторюватиметься n₂ разів, і т.д. Отже, кількість розкладань:

.