Учебное пособие: Елементи комбінаторики. Початки теорії ймовірностей

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

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

Наприклад, з елементів множини А = {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 = 3628800.

§ 3. Розміщення

Нехай деяка множина складається з п різних елементів.

Означення. Розміщеннями з п елементів по kназиваються підмножини, що мають kелементів, вибраних з даних п елементів і розміщених у певному порядку (k<п).

Розміщення можуть відрізнятися одне від одного або самими елементами, або порядком їх розміщення.

Наприклад, нехай маємо три елементи: 1, 2, 3. Тоді розміщення з трьох елементів по два мають вигляд: (1, 2), (1, 3), (2, 1), (3, 1), (2, 3), (З, 2). Розміщення (1, 2) і (2, 1) відрізняються лише порядком. Вони утворюють два різних числа 12 та 21. Розміщення (1, 2) і (1, 3) відрізняються самими елементами. Вони утворюють два різних числа 12 і 13.

Кількість розміщень з даних п елементів по kпозначають через А^k _n , = k < п.

Доведемо, що

А^k _n = n(n-1)(n-2)...(n-(k-1)).(1)

Якщо множина містить п елементів, то при утворенні розміщень по одному елементу таких розміщень буде п (стільки, скільки елементів у множині). Отже, А^k _n = п.