Означення. Перестановками з n елементів називаються розміщення з n елементів по n елементів.
Перестановки є окремим випадком розміщень. Оскільки перестановка містить всі n елементів множини, то різні перестановки відрізняються одна від другої тільки порядком елементів. Можна сказати, що перестановка - це кількість різних способів, якими можна упорядкувати n елементну множину.
Число перестановок з n елементів позначають символом Рn (Р - перша буква французького слова реrmutation - перестановка).
Оскільки за означенням Рn =
, то формули для обчислення числа перестановок з n елементів можна безпосередньо одержати а формули числа розміщень з n елементів по m елементів, замінивши в них m на n:
Рn == n(n-1)(n-2)…3×2×1=n!
або Рn ==
(1)
Отже, справедлива теорема
Теорема 3. Число перестановок з n елементів дорівнює добутку всіх натуральних чисел від 1 до n:
Рn=1×2×3 … (n-1)n=n!
Звідси маємо, що у множині, яка містить n елементів, встановити певний порядок слідування елементів, тобто упорядкувати n-елементну множину можна n! способами.
Теорему 3 можна довести незалежно від розміщення. Розглянемо всі можливі перестановки з n елементів і полічимо, скільки в них на першому місці один i той же елемент. Якщо поставити названий елемент перед кожною перестановкою а інших елементів, то одержимо всі можливі перестановки, які починаються з даного елемента. Отже, число всіх перестановок з n елементів, які починаються з даного елемента, дорівнює Рn-1. Але тоді число всіх перестановок з n елементів буде дорівнювати
Рn= n × Рn-1, (2)
бо кожний з n елементів може бути першим.
Користуючись формулою (2), можна далі довести теорему 3 методом математичної індукції.
1) формула (1) вірна при n=1, бо один елемент може знаходитись лише на першому місці, тобто Р1=1.
2) Припустимо, що формула (1) вірна при n=k, тобто, що
Рk = k! =1×2× … × k
3) Доведемо, що формула (1) вірна тоді і при n=k+1, тобто, що Рk+1 = (k+1)! =1×2×3× … × k×(k+1).
Дійсно, за формулою (2)
Рk+1 = (k+1) Рk =1×2× … × k×(k+1).
4) На основі принципу математичної індукції випливає, що формула (1) вірна для будь-якого натурального значення числа n.
Приклад 1. Скількома способами можна поставити на полиці 6 різних книг?
Розв'язання. Число таких способів дорівнює числу перестановок з шести елементів без повторення, тобто
Р6 = 1×2 × 3 × 4 × 5 × 6 = 720 (способами).
Відповідь. 720.
Приклад 2. Скількома способами можна розташувати пшеницю, жито, овес і ячмінь на чотирьох полях?
Розв’язання. Число таких способів дорівнює числу перестановок з чотирьох елементів без повторення.
Р
= 1×2 × 3 × 4 = 24
Відповідь.24 способа.
У розглянутих перестановках без повторення число перестановок з n елементів дорівнює n!. Але якщо серед даних n елементів є однакові, то перестановки , які утворюються одна з одної переставленням однакових елементів, нічим не відрізняються; том цьому випадку кількість різних перестановок буде меншою ніж n!