ПРЕЗЕНТАЦІЯ
На тему “Елементи комбінаторики. Перестановки, розміщення, комбінації”
����
ЕЛЕМЕНТИ КОМБІНАТОРИКИ. ПЕРЕСТАНОВКИ, РОЗМІЩЕННЯ, КОМБІНАЦІЇ.������
ТЕМА ЛЕКЦІЙНОГО ЗАНЯТТЯ:�
МЕТА ЗАНЯТТЯ:
ПЛАН:
Комбінаторика:
Повторення оглядово: множини і операції над ними:
Основні формули комбінаторики:
Перестановки, приклади Виконання вправ
Розміщення , приклад1, приклад2 Виконання вправ
Комбінації, приклад Виконання вправ
Основні закони комбінаторики:
Зміст матеріалу Приклади Виконання вправ
Підсумок заняття
Термін «комбінаторика» був введений в математичний ужиток Лейбніцем, який в 1666 році опублікував свою працю «Міркування про комбінаторне мистецтво».
Готфрід Вільгельм Лейбніц (Gottfried Wilhelm von Leibniz) - німецький філософ, математик, механік, юрист, дипломат.
Комбінаторика – важливий розділ математики, знання якого необхідно представникам різноманітних спеціальностей.
З комбінаторними задачами доводиться мати справу фізикам, хімікам, біологам, лінгвістам, спеціалістам по кодам та ін. Комбінаторні методи лежать в основі рішення багатьох задач теорії ймовірностей та її застосувань.
На практиці часто доводиться відповідати на запитання: скількома способами можна виконати певне завдання? Наприклад, скласти розклад п'яти уроків на день із десяти різних навчальних предметів; позначити різні зв'язки між атомами і молекулами певної речовини; записати діагоналі опуклого десятикутника; знайти різні шляхи доставки виробів із заводу в магазини і визначити, який з них найбільш вигідний.
Методи розв'язування таких задач вивчають у розділі математики, який називається комбінаторикою, а самі задачі — комбінаторними.
Розв'язуючи комбінаторні задачі, розглядають скінченні множини, утворені з елементів будь-якої природи, та їх підмножини. Залежно від умови задачі розглядаються скінченні множини, у яких істотним є або порядок елементів, або їх склад, або і те і те одночасно. Такі скінченні множини (сполуки) мають певну назву.
Приклади комбінаторних задач:
ПОВТОРЕННЯ
Множина може містити будь-яку кількість елементів. Якщо множина містить скінчене число елементів, то вона називається скінченною множиною.
Якщо ж число елементів множини нескінчене, то і множина називається нескінченною.
Якщо множина не містить жодного елемента, то таку множину називають порожньою і позначається Ø .
Якщо множини складаються з одних і тих же елементів, то такі множини називаються рівними.
Наприклад: {12; 13; 14; 15} = {15; 14; 13; 12}.
Розглянемо операції об'єднання, перетину і віднімання множин:
Об'єднанням множин А і В називають множину A∪B, що складається з усіх елементів, які належать хоча б одній з множин А, В.
Перетином множин А і В називають множину A ∩ B, яка складається з елементів, які належать як множині А, так і множині В.
Різницею множин А і В, називають множину A \ B, що складається з усіх елементів множини А, які не належать множині В.
Вправи:
Дано множини A = {2; 3; 4}, B = {0; 2; 4; 6}.
Знайти:
1)
2)
3)
Відповіді:
1)
2)
3)
ФАКТОРІАЛ�
Означення 1. Факторіал — це добуток послідовних натуральних чисел. n! = 1 ∙ 2 ∙ 3 ∙ ... ∙ n.
Наприклад : 1! = 1;
2! = 1 ∙ 2 = 2;
3! = 1 ∙ 2 ∙ 3 = 6;
4! = 1 ∙ 2 ∙ 3 ∙ 4 = 3! ∙ 4 = 24.
Приймають, що 0! = 1.
Термін «факторіал» походить від англійського слова «фактор» — множник.
ПРИКЛАДИ
1) Обчислити:
2) Спростити:
ПЕРЕСТАНОВКИ
Означення 2. Будь-яка впорядкована множина, що складається з n елементів, називається перестановкою з n елементів.
Перестановки відрізняються одна від одної лише порядком елементів.
Приклад 1. Із елементів множини А = {2, 4, 5} можна утворити 6 перестановок: {2, 4, 5}, {2, 5, 4}, {4, 2, 5}, {4, 5, 2}, {5, 4, 2}, {5, 2, 4}.
Кількість усіх можливих перестановок у множині з n елементів позначається Рn. Обчислюється за формулою:
Рn = n!
Приклад 2. 12 осіб можна розмістити за столом, біля якого поставлено 12 стільців, РІ2= 12! способами.
Рn = n!
ВПРАВИ�НА ЗАКРІПЛЕННЯ ФОРМУЛИ ЧИСЛА ПЕРЕСТАНОВОК
РОЗВ'ЯЗАННЯ
Обчисліть:
РОЗВ'ЯЗАННЯ
Обчисліть:
РОЗВ'ЯЗАННЯ
Скількома способами можна розсадити 7 осіб на семи вільних стільцях?
Щоб обчислити скільки способів існує для того щоб розсадити 7 осіб на семи вільних стільцях треба знайти число перестановок :
РОЗМІЩЕННЯ
Приклад 2: Скількома способами можна розсадити 4 студента на 25 місцях?
Відповідь: = 303 600.
ВПРАВИ�НА ЗАКРІПЛЕННЯ ФОРМУЛИ РОЗМІЩЕННЯ ЕЛЕМЕНТІВ
РОЗВ'ЯЗАННЯ
Обчисліть:
РОЗВ'ЯЗАННЯ
Обчисліть:
РОЗВ'ЯЗАННЯ
Розв'яжіть рівняння:
Розв'язати рівняння означає знайти змінну x.
Тобто тоді
Отже враховуюче, що x – натуральне число, отримаємо x=1.
Відповідь: 1
РОЗВ'ЯЗАННЯ
Кожен вибір трьох медалістів з 10 учасників відрізняється один від одного складом і порядком розташування учасників, тоді треба обчислити число розміщень з 10 по 3:
КОМБІНАЦІЇ
Означення 4. Будь-яка не упорядкована підмножина з m елементів даної множини М, що містить n елементів, де m ≤ n, називається комбінацією з n елементів по m.
Порядок елементів у множині неістотний, комбінації відрізняються лише складом елементів. Кількість усіх можливих комбінацій з n елементів по m позначається символом
Комбінація відрізняється від розміщення тим, що у цій підмножині неістотним є порядок елементів.
У загальному випадку кількість комбінацій з n елементів по m елементів можна обчислити за формулою:
Приклад: Скількома різними способами можна вибрати з 15 осіб делегацію в складі 3 осіб?
Розв'язання:
Різними вважатимемо ті делегації, які відрізняються хоча б однією особою. Отже, треба обчислити
Відповідь. Існує 455 способів.
ВПРАВИ�НА ЗАКРІПЛЕННЯ ФОРМУЛИ РОЗМІЩЕННЯ ЕЛЕМЕНТІВ
РОЗВ'ЯЗАННЯ
Обчисліть:
РОЗВ'ЯЗАННЯ
Обчисліть:
РОЗВ'ЯЗАННЯ
Скільки прямих можна провести через 7 точок, з яких ніякі три не лежать на одній прямій?
Кожні дві точки визначають одну пряму, і при цьому не відіграє ролі в якому порядку вони взяті. Тому число прямих дорівнює числу комбінацій з 7 по 2, тобто
ПРАВИЛА СУМИ І ДОБУТКУ
Комбінаторні задачі бувають різних видів. Але більшість із них розв'язують за допомогою двох основних правил: правила суми і правила добутку.
Вибір правила
Правило суми:
Або елемент a або елемент b.
Якщо елемент a можна вибрати m способами, а елемент b – n способами, то вибір a або b можна здійснити (m+n) способами.
Правило добутку:
І елемент a і елемент b.
Якщо елемент a можна вибрати m способами, а елемент b – n способами, то вибір a і b можна здійснити (m*n) способами.
ПРИКЛАДИ
Приклад 1: У групі 9 дівчаток і 11 хлопців. Скількома способами можна вибрати 1 студента для роботи біля дошки?
Розв'язання: Для роботи біля дошки ми можемо вибрати дівчинку 9 способами або хлопця 11 способами.
Загальна кількість способів дорівнює 9 + 11 = 20.
Приклад 2: На вершину гори ведуть 5 доріг. Скількома способами можна піднятися на гору і спуститися з неї?
Розв'язання : Для кожного варіанту підйому на гору існує 5 варіантів спуску з гори. Значить всіх способів піднятися на гору і спуститися з неї 5 ∙ 5 = 25.
ВПРАВИ�НА ЗАКРІПЛЕННЯ ФОРМУЛИ КОМБІНАЦІЇ ЕЛЕМЕНТІВ
1) 7 книг різних авторів і трьохтомник одного автора розташовані на книжковій полиці. Скількома способами можна розставити ці 10 книжок на полиці так, щоб книги автора трьохтомника стояли поруч? Розв'язання
2) Збори з 30 осіб обирають голову, секретаря та трьох членів редакційної комісії. Скількома способами це можна зробити?
3) У підрозділі 60 солдат і 5 офіцерів. Скількома способами можна виділити наряд, який складається із трьох солдат і одного офіцера?
РОЗВ'ЯЗАННЯ
7 книг різних авторів і трьохтомник одного автора розташовані на книжковій полиці. Скількома способами можна розставити ці 10 книжок на полиці так, щоб книги автора трьохтомника стояли поруч?
РОЗВ'ЯЗАННЯ
Збори з 30 осіб обирають голову, секретаря та трьох членів редакційної комісії. Скількома способами це можна зробити?
РОЗВ'ЯЗАННЯ
У підрозділі 60 солдат і 5 офіцерів. Скількома способами можна виділити наряд, який складається із трьох солдат і одного офіцера?
ДОМАШНЄ ЗАВДАННЯ
ПІДСУМОК ЗАНЯТТЯ
На сьогоднішньому занятті ви взнали:
1) Що це за наука комбінаторика? Які задачі називають комбінаторними?
Дедалі частіше в житті приходиться розв'язувати задачі, головним питанням у яких є: «Скількома способами це можна зробити?»
• Скільки прямих можна провести через 7 точок, з яких ніякі три не лежать на одній прямій?
• Скількома способами можуть бути присуджені золота, срібна або бронзова медалі трьом учасникам з 10?
• Скількома способами можна розсадити 7 осіб на семи вільних стільцях?
У цих задачах задано елементи для комбінування і вимагається знайти кількість можливих комбінацій.
Вибір формули
Чи враховується порядок розміщення елементів?
так
ні
Чи всі елементи входять в сполуку
Комбінації
так
ні
Переставновки
Рn = n!
Розміщення
2) А також взнали і навчилися розрізняти види сполук (перестановки, розміщення, комбінації).
3) взнали і навчилися розрізняти два основні правила комбінаторики.
Вибір правила
Або a або b
І a і b
Якщо елемент a можна вибрати m способами, а елемент b – n способами, то вибір a або b можна здійснити (m+n) способами.
Якщо елемент a можна вибрати m способами, а елемент b – n способами, то вибір a і b можна здійснити (m*n) способами.
ДЯКУЮ
ЗА
ЗАНЯТТЯ