Презентації до теми: "Комбінаторика"
Елементи комбінаторики перестановки
* 1 2 3 2 3 4 1 3 4 1 2 4 4 1 2 3 Всього 4∙3=12 Від турбази до гірського озера ведуть 4 стежки. Скількома способами туристи можуть відправитися в похід до озера,якщо вони не хочуть спускатися тією ж стежкою, котрою піднімалися?
* 1 2 3 2 3 4 1 3 4 1 2 4 4 1 2 3 Сходження на гору - 4 варіанти Спуск з гори - 3 варіанти 12 – число всіх можливих випадків проведення n випробувань
Задача. В сім*ї 6 осіб, а за столом в їдальні 6 стільців. В сім*ї вирішили щовечора за вечерею сідати на ці 6 стільців по-новому. Скільки днів члени сім*ї зможуть робити це без повторень? - 6 варіантів вибору стільця - 5 варіантів вибору стільця (1 вже зайнятий) - 4 варіанти вибору стільця (2 вже зайняті) - 3 варіанти вибору стільця (3 вже зайняті) - 2 варіанти вибору стільця (4 вже зайняті) - 1 варіант вибору стільця (5 вже зайнято)
Правило добутку (число всіх можливих результатів незалежного проведення n випробувань дорівнює добутку кількості цих випробувань) Різних способів розташування за столом6∙5∙4∙3∙2∙1=720
Застосовуючи правило добутку, доволі часто в певних задачах зустрічаються такі добутки: 1∙2 1∙2∙3 1∙2∙3∙4 1∙2∙3∙4∙5 1∙2∙3∙4∙5∙6 1∙2∙3∙4∙5∙6∙7
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
Добуток послідовних перших n натуральних чисел позначають n! НАЗИВАЮТЬ «ен факторіал» Одне зі значень слова «factor»-«множник». Так що «ен факторіал» приблизно перекладається як «складений з n множників»
Вказати порядок розташування елементів у скінченній множині з n елементів означає поставити у відповідність кожному елементу множини певне натуральне число від 1 до n. Будь-яка впорядкована множина,яка складається з n елементів,називається перестановкою з n елементів.
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 Наприклад, всі перестановки множини з трьох елементів:
Pn = n! Число перестановок множини з n елементів позначають Рn Теорема «Про кількість перестановок» Число всіх перестановок n-елементної множини дорівнює n!
Приклад 1 Три ведмеді по одному вибігають з хатини, доганяючи дівчинку. Скількома способами вони можуть вибігти? Порядок вибігання з хатини задається умовою 1,2,3. Це елементи множини,тоді число перестановок P3 = n! = 3! = 6. – (шукана кількість способів)
Приклад 2 Скількома способами чотири злодії можуть по одному розбігтися на всі чотири сторони.Порядок вибігання на всі чотири сторони задається напрямком П,П,З,і С Задається умовою 1,2,3,4. Це елементи множини, тоді число перестановок P4 = n! = 4! = 24. – (шукана кількість способів)
Приклад 3 Одинадцять футболістів шикуються перед початком матчу. Першим – обов*язково капітан, другим–обов*язко воротар, інші–випадковим чином. Скільки існує способів шикування. Дев*ять футболістів (всіх, крім капітана і воротаря потрібно розставити на дев*ять місць, з третього по одинадцяте.. Порядок розташування задається умовою 1-9. Це елементи множини, тоді число перестановок P9 = n! = 9! = 362 880. – (шукана кількість способів)
Елементи комбінаторики РОЗМІЩЕННЯ
Порівняйте 2 ЗАДАЧі: Задача 1. Маємо 4 кулі і 4 порожніх комірки в коробці. Скільки варіантів розташування кульок можна отримати? Задача 2. Маємо 4 кулі і 3 порожні комірки в коробці Які варіанти розміщення кульок можна отримати?
Розв*язування 1 задачі: Порядок розташування кульок задається умовою 1,2,3,4. Це елементи множини,тоді число перестановок P4 = n! = 4! = 24. – (шукана кількість способів)
Позначається читають: «A з n по k» Відмінність від попередньої задачі: кількість кульок перевищує кількість комірок.Тобто неможливо застосувати теорему про кількість перестановок. Розміщенням з n елементів по k (k ≤ n) називається будь-яка множина, яка складається з будь-яких k елементів, взятих в певному порядку з заданих n елементів.
c b d c b a d b a b c a d c a b d a c d a a c b d c b d a b a d b c d b b a c c a b d a c d b c a b c b d c a d c b a d c a d a b d b c d a c d Розглянемо 1 спосіб розв*язування задачі 2. Надамо кулькам позначення а, b, c, d.
* a b c b c d a c d a b d d a b c Розв*яжемо цю задачу, використовуючи дерево варіантів.
зазначимо, що для кожного вибраного першого елемента можна трьома способами вибрати з трьох елементів, що залишилися, другий елемент. Далі, для кожних перших двох елементів можна двома способами вибрати з залишених елементів третій елемент.
Розв*язок 2 задачі: Розміщення 4 елементів по 3. Кількість множників дорівнює 3
1 елемент 2 елемент 3 елемент 4 елемент K- елемент n способів n-1 способів n-2 способів n-3 способів n – (k-1) способів з n елементів множини з n-2 елементів множини з n-3 елементів множини з n-(k-1) елементів множини з n-1 елементів множини Міркуючи аналогічно, підрахуємо скільки можна скласти розміщень з n елементів по k , де k≤n.
Правило обрахування розміщень з n елементів по k елементів
В даному випадку k=2, тому кількість множників у формулі дорівнює 2,значить: Приклад 1 В групі 27 учнів. До дошки потрібно викликати двох. Скількома способами це можна зробити, якщо перший учень повинен розв*язати задачу з геометрії, другий – з алгебри? Порядок вибору двох елементів множини з 27 елементів важливий, тому:
В даному випадку k=3, тому кількість множників у формулі дорівнює 3,значить: Приклад 2 В групі 27 учнів, з яких потрібно вибрати трьох. . Перший учень повинен розв*язати задачу, другий – сходити за крейдою, третій – чергувати в їдальню. Скількома способами це можна зробити? Порядок у множині з 27 елементів важливий, тому:
В даному випадку k=2, тому кількість множників у формулі дорівнює 2,значить: Приклад 3: Із 30 учнів групи потрібно вибрати старосту групи та замісника старости групи. Скількома способами це можна зробити?
Питання дня: Як відрізнити задачу на перестановки від задачі на розміщення Кількість даних елементів множини співпадає з початковою кількістю елементів меньше початкової кількості елементів
Елементи комбінаторики
Маємо п*ять гвоздик різного кольору: a, b, c, d, e. Потрібно скласти букет з трьох гвоздик. Якщо в букет входить гвоздика a, то можна скласти такі букети: abc, abd, abe, acd, ace, ade Якщо в букет не входить гвоздика a, але входить гвоздика b, то можна скласти такі букети: bcd, bce, bde Якщо в букет не входять ні гвоздика a, ні гвоздика b, можливий один варіант складення букета c, d, e
Вказали всі можливі способи складання букетів, в котрих по-різному комбінуються три гвоздики з даних п*яти Склали всі можливі КОМБІНАЦІЇ з 5 елементів по 3 елементи. Позначають: В даному прикладі
Розглянемо множину,яка складається з n елементів, і з його елементів складені всі можливі комбінації по k елементів. Число таких комбінацій дорівнює В кожній комбінації можно виконати перестановок Рk В результаті отримаємо всі розміщення , котрі можна скласти з n элементів по k Їх число дорівнює значить Звідси
Тобто: Нескладні перетворення приводять отриману формулу до вигляду: Запам;ятаємо 0!=1
Приклад 1: Із 15 членів туристичної групи потрібно вибрати 3 чергових. Скількома способами це можна зробити? Мова йде про комбінації з 15 елементів по 3.
Приклад 2: З вази з фруктами, в котрій лежать 9 яблук і 6 груш, потрібно вибрати 3 яблука і 2 груші. Скількома способами можно зробити такий вибір? Вибрати 3 яблука з 9 можна способами, А вибрати 2 груші з 6 можна способами. Таким чином, враховуючи правило добутку, вибір, що відповідає умові задачі, можна зробити
про публікацію авторської розробки
Додати розробку