Перестановки без повторень.

Нехай фіксована впорядкована n-множина. Впорядкована k-підмножина з елементів цієї множини називається k-перестановкою. Іншим словами k-перестановка – це розташовані визначеному порядку k елементів а₁, а_{2 ,...,} а_n множини М.

Дві k-перестановки вважаються різними, якщо:

1. Вони відрізняються хоча б одним елементом;

2. Елементи співпадають, проте розташовані вони на різних місцях.

Приклад.Нехай , 2 - перестановками множини М є (1, 2);(2, 1); (1, 3); (3, 1); (3, 2); (2, 3). 3 - перестановки (1,2,3); (3,2,1); (2,3,1)....

Добуток 1, 2, 3 ... n позначимо n! Вважаємо , що 0! = 1

Позначимо через - число всіх різних k–перестановок з n різних елементів та підрахуємо число таких перестановок .

Перший елемент будь-якої такої k-перестановки може бути вибраний n способами. Після цього другий її елемент може бути вибраний (n-1) різними способами і т.д. k-ий елемент може таким чином бути вибраний (n-k+1) способами. Використовуючи правило добутку відповідне число раз отримаємо:

(1)

у випадку, коли n = k

(2)

Для числа перестановок справедливо наступне рекурентне співвідношення:

(3)

Справедливість цього співвідношення можна обґрунтувати комбінаторними міркуваннями. Число всіх перестановок дорівнюється сумі числа перестановок, які містять елемент 1 та числа всіх перестановок, які не містять елемент 1 (за правилом суми). Якщо елемент 1 входить до k-перестановки Х, то він сам може займати в ній кожне з k місць. Інші n-1 елементів множини M утворять у ній k-1 перестановку. За правилом перестановки одержуємо, що число перестановок з 1 дорівнює . Якщо 1 не входить в Х , тоді Х є k-перестановкою (n-1) множини М\{1}; число таких k–перестановок дорівнює .

ПрикладВ групі 25 студентів. Необхідно обрати старосту, замісника старости та профорга. Кількома способами можна це зробити?

Ці три посади складають впорядковану підмножину множини студентів. Тому вони складають 3-перестановку множини з 25 елементів.