��Комбінаторика та правила суми і добутку.�Розміщення, перестановки та комбінації.� �
Базові поняття комбінаторики і розраховані результати з'явилися ще в стародавньому світі.
В 6-му столітті до н.е. індійський лікар Сушрут в своїй праці наводить, що із 6-ти різних смаків можна утворити 63 різні комбінації.
Вільгельм Лейбніц та Блез Паскаль вважаються основоположниками сучасної комбінаторики.
Сам термін «комбінаторика» придумав Лейбніц.
Учень Лейбніца Якоб Бернуллі, один із засновників теорії ймовірностей, виклав у своїй книзі «Мистецтво припущень» (1713) безліч відомостей з комбінаторики.
Блез Паскаль
Вільгельм Лейбніц
Якоб Бернуллі
Комбінаторикою називають розділ дискретної математики, присвячений розв'язанню задач про вибір та розміщення елементів скінченної множини згідно із заданими правилами.
ПРАВИЛО ДОДАВАННЯ
Якщо дві взаємовиключні події можуть бути виконані відповідно k та m способами, тоді якусь одну з цих подій можна виконати k+m способами.
З міста А в місто В можна добратися 2 потягами, 3 літаками, 4 автобусами. Скількома способами можна добратися з міста А у місто В?
Розв'язання. N=2+3+4=9.
№ 602. У класі 11 хлопців і 10 дівчат. Скількома способами можна делегувати одного учня в шкільний комітет самоврядування?
Відповідь: 11+10 = 21 способами.
№ 607. У магазині є три види печива і десять видів цукерок. Сергій хоче купити сестрі або печиво, або цукерки. Скількома способами він може це зробити?
Відповідь: 3 + 10 =13 способами.
ПРАВИЛО МНОЖЕННЯ
Нехай дві виконувані одна за одною дії можуть бути здійснені відповідно k та m способами. Тоді обидві вони можуть бути виконані k·m способами.
У турнірі беруть участь 8 команд з хокею. Скільки існує способів розподілити перше, друге та третє місця?
Розв'язання. N=8·7·6=336
№ 609. На вершину гори ведуть 4 стежки. Скількома маршрутами турист може піднятися на гору та спуститися з неї, обираючи для спуску й підйому різні стежки?
1
2
4
3
2
3
4
1
2
3
4
1
3
2
4
1
2
3
4
1
4·3=12
Діаграма “дерево”
№ 603. У класі 11 хлопців і 10 дівчат. Скількома способами можна делегувати двох учнів в шкільний комітет самоврядування?
Відповідь: 21·20 = 420 способами.
№ 604. У класі 12 хлопців і 10 дівчат. Скількома способами можна делегувати одну дівчину та одного хлопця в шкільний комітет самоврядування?
Відповідь: 12·10 = 120 способами.
№ 614. Скільки трицифрових чисел можна утворити з цифр 1, 2, 3, 4, 5?
Відповідь: 5 · 4 · 3 = 60 чисел.
№ 611. Скількома способами 5 осіб можуть утворити чергу до каси?
Відповідь: 5! = 120.
№ 612. Скільки різних речень можна написати словами “ми”, “любимо”, “грати”? А словами “ми”, “дуже”, “любимо”, “грати”?
Відповідь: 3! = 6, 4! = 24.
Факторіал натурального числа n це добуток натуральних чисел від одиниці до n включно, позначається n!.
n! = 1·2·3·…. ·n
2.(Р10 = 10! = 3628800)
Перестановкою (the permutation) із m елементів називається будь-яка скінченна послідовність, яка одержується в результаті упорядкування деякої скінченної множини, складеної з m елементів.
Число всіх перестановок із m елементів позначається Рm.
Це слово походить від латинського factor, що означає “множник”.
Перестановка
№ 615. Обчисліть: а) 10! : 5!; б) 13! : 10!; в) 20! : 25!; г) 100! : 97!.
№ 606. Спростіть вираз: а) n! · (n + 1); б) n · (n – 1)!; в) (n + 1)! : n!; г) n! : n.
Сполучення (комбінації)
Будь-яка підмножина множини М, яка містить k елементів (n=0, 1, 2, ..., n), називається сполученням (combination) або комбінацією з даних m елементів по n елементів, якщо ці підмножини відрізняються хоча б одним елементом.
Число різних сполучень із n елементів по k позначається
1.Скількома способами можна вибрати три
цифри з дев'яти 1, 2, 3,...,9?
652. У класі 32 учні. Скількома способами можна вибрати з них двох чергових?
3. На колі розміщено 9 точок. Скільки існує відрізків, які з’єднують кожну точку з іншою?
Розміщеннями з n елементів по m називаються такі сукупності m елементів, що відрізняються одна від іншої принаймні одним елементом або порядком їх входження (n ≤ m):�
Розміщення
1. Скільки різних трицифрових чисел можна скласти за допомогою цифр від 1 до 9?
642. На тарілці є 7 груш. 5 дітей мають взяти з тарілки по одній груші. Скількома способами це можна зробити?
656. На кожній із пяти карток написано одну з цифр 1, 2, 3, 4, 5. Скільки з цих карток можна скласти різних чисел: а) двоцифрових; б) трицифрових; в) чотирицифрових?
Вибір формули для розв’язування комбінаторної задачі.
Комбінація | Розміщення |
1.Скількома способами можна вибрати три цифри з дев'яти 1, 2, 3,...,9? 2. У класі 32 учні. Скількома способами можна вибрати з них двох чергових? 3. На колі розміщено 9 точок. Скільки існує відрізків, які з’єднують кожну точку з іншою? | 1. Скільки різних трицифрових чисел можна скласти за допомогою цифр від 1 до 9? 2. У класі 32 учні. Скількома способами можна вибрати з них старосту та заступника? 3. На тарілці є 7 груш. 5 дітей мають взяти з тарілки по одній груші. Скількома способами це можна зробити? |
До зустрічі!