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

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

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

Дві впорядковані множини називаються рівними, якщо вони складаються з тих самих елементів і однаково впорядковані. З цього випливає, що множини (а, b, с) і (b, с, а) — це різні впорядковані множини.

Означення. Будь-яка впорядкована множина, що складається з п елементів, називається перестановкою з п елементів.

Перестановки з п елементів складаються з одних і тих самих елементів, а відрізняються одна від одної лише порядком.

Наприклад, з елементів множини, А = {1, 2, 3} можна утворити шість перестановок: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).

Число перестановок у множині з п елементів позначають Р_п .

Доведемо, що Р_п =n!,(1).

де п! = 1*2* … *п .

Для доведення застосуємо метод математичної індукції.

• 1. Якщо п = 1, маємо Р_п =1 = 1!; тобто формула (1) виконується.
• 2. Припустимо, що для n = 1 рівність Р_к = k! виконується (п і kнатуральні числа).

Доведемо, що для п = k +1 виконуватиметься рівність Р_{k +1} =(к + 1)!

На перше місце можемо поставити будь-який з k+ 1 елементів множини. Тоді kмісць, які залишилися, можна задавати будь-якою перестановкою з kелементів. Число таких перестановок Р_k. Таким чином, перестановку з k + 1 елемента даної множини можна розглядати як пару: на першому місці - елемент множини, на другому — перестановка з kелементів, що залишились (таких перестановок Р_k). На підставі принципу добутку число всіх перестановок (всіх таких пар) Р_{k +1} =(к + 1) Р_k ,(1).

З формули (2) дістаємо Р_{k +1} =(к + 1) Р_k = Р_k * (к + 1) =k! * (k+1)=1*2*…*k* (k+1)=(k+1)!

Приклад 1. Скількома способами можна розмістити в один ряд червону, синю, чорну та зелену фішки?

Р₄ = 4! = 1*2*3*4 = 24.

Приклад 2. Скількома способами можна розмістити за столом 10 чоловік?

Р₁₀ =10! = 1*2*3*4*5*6*7*8*9*10 = 3 628 800.