Презентація "Перестановки"

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

Області застосування комбінаторики Спортивні змагання (розрахунок кількості ігор між учасниками) Хімія (аналіз можливих зв'язків між хімічними елементами) Економіка (аналіз варіантів купівлі-продажу) Доставка пошти (розгляд варіантів пересилання) Військова справа (розташування підрозділів)

Перестановкою (the permutation) із n елементів називається будь-яка скінченна послідовність (progression), яка одержується в результаті упорядкування деякої скінченної множини, складеної з n елементів. Число всіх перестановок із n елементів позначається Рn. Це число дорівнює добутку всіх цілих чисел від 1 до n. Позначають: Добуток n перших натуральних чисел прийнято позначати символом n! Символ n! читають "eн факторіал". Це слово походить від латинського factor, що означає “множник”.  При n=1 у виразі   залишається одне число 1. Тому приймається (як визначення), що 1!=1. При n=0 вираз   немає змісту, з числа 0 існує одне переміщення, тому приймається, що 0!=1. Значить, Рn=n!  Приклад. Якою кількістю способів можна розсадити 8 студентів в ряд з 8 місць:

Від турбази до гірського озера ведуть 4 стежки. Скількома способами туристи можуть відправитися в похід до озера, якщо вони не хочуть спускатися тією ж стежкою, якою піднімалися? * 1 2 3 2 3 4 1 3 4 1 2 4 4 1 2 3 Всього 4∙3=12

12 – число всіх можливих випадків проведення n випробувань * 1 2 3 2 3 4 1 3 4 1 2 4 4 1 2 3 Сходження на гору - 4 варіанти Спуск з гори - 3 варіанти

Задача. В сім'ї 6 осіб, а за столом в їдальні 6 стільців. В сім'ї вирішили щовечора за вечерею сідати на ці 6 стільців по-новому. Скільки днів члени сім'ї зможуть робити це без повторень? - 6 варіантів вибору стільця - 5 варіантів вибору стільця (1 вже зайнятий) - 4 варіанти вибору стільця (2 вже зайняті) - 3 варіанти вибору стільця (3 вже зайняті) - 2 варіанти вибору стільця (4 вже зайняті) - 1 варіант вибору стільця (5 вже зайнято)

Правило добутку (число всіх можливих результатів незалежного проведення n випробувань дорівнює добутку кількості цих випробувань) Різних способів розташування за столом6∙5∙4∙3∙2∙1=720

1∙2 = 2 1∙2∙3 = 6 1∙2∙3∙4 = 24 1∙2∙3∙4∙5 = 120 1∙2∙3∙4∙5∙6 = 720 1∙2∙3∙4∙5∙6∙7 = 5040

Наприклад, всі перестановки множини з трьох елементів: a c a b c b a a c b c b a a b c c b a c b a c b a b c a c b a b a c c b або 3∙2=6 або Перестановка із множини 3 елементів Р3=n!=3!=1∙2∙3=6

Приклад Три ведмеді по одному вибігають з хатини, доганяючи дівчинку. Скількома способами вони можуть вибігти? Порядок вибігання з хатини задається умовою 1,2,3. Це елементи множини,тоді число перестановок P3 = n! = 3! = 6. – (шукана кількість способів)

Приклад Скількома способами чотири злодії можуть по одному розбігтися на всі чотири сторони.Порядок вибігання на всі чотири сторони задається напрямком П,П,З,і С Задається умовою 1,2,3,4. Це елементи множини, тоді число перестановок P4 = n! = 4! = 24. – (шукана кількість способів)

Приклад Одинадцять футболістів шикуються перед початком матчу. Першим – обов'язково капітан, другим–обов'язко воротар, інші–випадковим чином. Скільки існує способів шикування. Дев'ять футболістів (всіх, крім капітана і воротаря потрібно розставити на дев'ять місць, з третього по одинадцяте.. Порядок розташування задається умовою 1-9. Це елементи множини, тоді число перестановок P9 = n! = 9! = 362 880. – (шукана кількість способів)

Приклад Державні прапори деяких країн складаються з трьох горизонтальних смуг різного кольору. Скільки існує різних варіантів прапорів з білою, синьою і червоною смугою? Це елементи множини, тоді число перестановок P3 = n! = 3! = 6. – (шукана кількість варіантів)

Розв'яжи самостійно