ожини певне натуральне число від 1 до п.
Дві впорядковані множини назіваються рівнімі, ЯКЩО смороду складаються з тихий самих ЕЛЕМЕНТІВ и однаково впорядковані. З цього віпліває, что множини (а, b, с) і (b, с, а) - це Різні впорядковані множини.
Означення. Будь-яка впорядкована множини, что Складається з п ЕЛЕМЕНТІВ, назівається перестановка з п ЕЛЕМЕНТІВ.
Перестановки з п ЕЛЕМЕНТІВ складаються з одних и тихий самих ЕЛЕМЕНТІВ, а відрізняються одна від одної позбав порядком.
Наприклад, з ЕЛЕМЕНТІВ множини А = {1, 2, 3} можна утворіті Шість перестановок: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). p> Число перестановок у множіні з п ЕЛЕМЕНТІВ позначають Р п . p> Доведемо, что
Р п = n!, (1)
де п! = 1 • 2 • ... • п. p> Для доведення застосуємо метод математичної індукції.
1. Если п = 1, маємо Р п = 1 = 1!; Тоб формула (1) віконується.
2. Припустиме, что для n = 1 Рівність Р до = k! віконується (п і k - натуральні числа).
Доведемо, что для п = k +1 віконуватіметься Рівність
Р k +1 = (до + 1)! br/>
На перше місце Можемо поставити будь-який з 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)! p> Приклад 1. Скількома способами можна розмістіті в один ряд червону, синю, чорну та зелену фішки?
Р4 = 4! = 1 • 2 • 3 • 4 = 24. br/>
Приклад 2. Скількома способами можна розмістіті за столом 10 мужчина?
Р 10 = 10! = 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 = 3628800. p> В§ 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. p> Кількість розміщень з даніх п ЕЛЕМЕНТІВ по k позначають через А k n , = k <п.
Доведемо, что
А k n = n (n-1) (n-2) ... (n-(k-1)). (1)
Если множини містіть п ЕЛЕМЕНТІВ, то при утворенні розміщень по одному елементами таких розміщень буде п (стількі, Скільки ЕЛЕМЕНТІВ у множіні). Отже, А k n = п.
Утворімо тепер размещения з п ЕЛЕМЕНТІВ по два. Для цього візьмемо п розміщень по одному Елемент и до шкірного размещения допішемо Кожний з решті п -1 ЕЛЕМЕНТІВ даної множини. Таким чином, А k n = n (n-1). p> Застосуємо метод математичної індукції. Припустиме, что для А 2 n правильною є формула (1). Размещения з п ЕЛЕМЕНТІВ по k + і можна розглядаті як пару: на первом місці будь-яке размещения з п ЕЛЕМЕНТІВ по k (їх кількість А k n ), на іншому - будь-який елемент з решти п - k ЕЛЕМЕНТІВ. За правилом добутку дістанемо
А n k +1 = А n k (nk) . (2)
користуючися формулою (1), маємо
А n k +1 = п (п-1) (п-2) ... (п-(k- і)) (п-k) == n (n - 1) (n - 2) ... (n-(k -1)) (n-(k +1-1)).
Оскількі
В
то формулу (1) можна записатися ще так:
. (3)
Приклад 1. Скількома способами можна вібрато з 10 кандидатів три особини на три Різні посади?
Для розв'язування задачі треба найти число розміщень з 10 ЕЛЕМЕНТІВ по три. Отже, за формулою (1) маємо
A 3 10 = 10 • 9 • 8 = 720. p> Приклад 2. Скільки трицифрового чисел з різнімі цифрами можна утворіті з цифр 0, 1, 2, 3, 4?
Загальна кількіс...
