Перестановки
Нехай треба підрахувати число способів, за якими можна розмістити в ряд 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 = 4! = 1•2•3•4 = 24.
Приклад 2. Скількома способами можна розмістити за столом 10 чоловік?
Р10=10! = 1•2•3•4•5•6•7•8•9•10 = 3628800.