Презентація "Елементи комбінаторики"

Елементи комбінаторики. Костюкевич П. П. НВК: ЗОШ №34 –економіко-правовий ліцей «Сучасник» м. Кропивницький

Правило суми. В комбінаториці правило суми — це основний комбінаторний принцип. Основна ідея в тому, що якщо у нас A способів зробити щось одне і B способів зробити щось інше, і ми не можемо робити їх одночасно, то існує A + B способів вибрати одну з дій. Простенький приклад. Жінка вирішила сьогодні зробити покупку в одному з магазинів: розташованому або в північній або в південній частині міста. Якщо вона відвідає північну частину міста, то вона може зробити придбання в торговому центрі, або в меблевому магазині, або у ювелірному магазині (3 способи). Якщо вона відвідає південну частину міста, то вона може зробити придбання або в магазині одягу або у взуттєвому магазині (2 способи). Таким чином, є 3 + 2 = 5 можливих варіантів вибору магазину, в якому жінка сьогодні зробить покупки.

ПРАВИЛО МНОЖЕННЯЯкщо потрібно виконати одну за одною дві дії, і першу з них можна виконати n способами, а другу, після виконання першої, m способами, тоді обидві ці дії (одну за одною) можна виконати m*n способами. Іншими словами: якщо в умові задачі використовується «І», то слід використовувати операцію множення

ЗНО 2015. В школі є два одинадцятих класи. В 11- А навчається 12 хлопців та 8 дівчат, а в 11 – Б – 9 хлопців та 15 дівчат. З учнів цих класів необхідно вибрати двох ведучих для проведення святкового вечора, причому хлопець має бути з 11 – А класу, а дівчинка – з 11 – Б класу. Скільки всього існує варіантів вибору ведучих?Перша дія – вибір хлопця з 11 А класу (n = 12)Друга дія – вибір дівчинки з 11 Б класу (m = 15)𝑛∙𝑚=12∙15=180 ЗАУВАЖЕННЯ. Важливою складовою комбінаторних задач є вміння обробляти інформацію з умови. Тобто відділяти те, що необхідно для розв'язання, від зайвої інформації. Наприклад, в цій задачі зайвою є інформація про кількість дівчат в 11 А та кількість хлопців в 11 Б 

ЗНО 2014. Студент на першому курсі повинен вибрати одну з трьох іноземних мов, яку буде вивчати та одну з п’яти спортивних секцій, яку відвідуватиме. Скільки всього існує варіантів вибору студентом іноземної мови та спортивної секції?𝑛=3 (вибір іноземної мови)𝑚=5 (вибір спортивної секції з урахуванням того, що обрано якусь іноземну мову)𝑛∙𝑚=3∙5=15 

Перестановки (без повторень)Перестановкою з n елементів називається будь-яка впорядкована множина з n елементів.{5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}Формула. Приклад 𝑃𝑛=𝑛!=1∙2∙3∙…∙𝑛 Кількість різних шестизначних чисел, які можна скласти з цифр 2, 4, 5, 6, 7, 9, що не повторюються дорівнює𝑃6=6!=1∙2∙3∙4∙5∙6=720{5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}Формула. Приклад

ЗНО 2010. Студенти однієї з груп під час сесії повинні скласти п’ять іспитів. Заступнику декана треба призначити складання цих іспитів на п’ять визначених дат. Скільки всього існує різних варіантів розкладу іспитів для цієї групи? Іспити в даному випадку – це елементи, які треба впорядкувати. Кількість 𝑛=5 Всього варіантів: 5!=1∙2∙3∙4∙5=120 

Розміщення (без повторень)Розміщенням з n елементів по k називається будь-яка впорядкована множина з k елементів, складена з елементів n-елементної множини.{5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}Формула. Приклад Кількість різних тризначних чисел, які можна скласти з цифр 2, 4, 5, 6, 7, 9 , якщо цифри не повторюються дорівнює

Сполучення (без повторень)Сполученням з n елементів по k називається будь-яка множина з k елементів, складена з елементів n-елементної множини.{5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}Формула. Приклад Із класу, що складається з 25 учнів, можна виділити 5 учнів для чергування в шкільній їдальні

Практичні способи обчислення кількості розміщень і сполучень𝐴103=10∙9∙8=720 𝐴𝑛𝑘 - це добуток 𝑘 множників, перший з яких дорівнює 𝑛, а кожний наступний на 1 менше за попередній 𝐶104=𝐴1044!=10∙9∙8∙71∙2∙3∙4=210  

Перестановки (з повтореннями){5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}Формула. Приклад 𝑃𝑛=𝑛!𝑘1!…𝑘𝑚! Кількість різних слів, які можна скласти з букв слова «КАНДАЛАКША» , дорівнює𝑃10=10!4!∙2!=75600{5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}Формула. Приклад

Розміщення (з повтореннями){5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}Формула. Приклад Скількома способами можна покласти 3 кульки у 5 коробок?

Сполучення (з повтореннями){5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}Формула. Приклад В шкільній їдальні є сосиски в тісті, пиріжки з картоплею та капустою. Скількома способами можна придбати 5 різних пиріжків?

Вибір формули

ЗНО 2016. У чайному кіоску в наявності є лише розфасований у коробки по 100 г листовий чорний чай 8 видів, серед яких є вид «чорна перлина». Покупець вирішив придбати в цьому кіоску для подарункового набору три коробки чорного чаю трьох різних видів, серед яких обов’язково повинен бути вид «чорна перлина». Скільки всього в покупця є варіантів такого придбання трьох коробок чаю для набору з наявних в кіоску?Інформація про те, що чай розфасовано у коробки по 100 г – зайва. Обирати, насправді, будемо не з 8, а з 7 видів (оскільки один фіксований). Причому обираємо не 3, а 2 види. Залишається розібратись – чи важливий порядок? Поставте себе на місце людини, яка отримає цей подарунковий набір. Чи важливо вам, в якому порядку ці коробки потрапляли до набору? Вам важливо, що ось вони є, і це саме ці три сорти. Отже, порядок не важливий. Використовуємо формулу сполучень 𝐶72=7∙61∙2=21 

ЗНО 2018. В Оленки є 8 різних фотографій з її зображенням та 6 різних фотографій її класу. Скільки всього в неї є способів вибрати з них 3 фотографії зі своїм зображенням для персональної сторінки в соціальній мережі та 2 фотографії свого класу для сайту школи?Нехай спочатку Оленка обирає 3 фотографії з власним зображенням (порядок вибору не важливий, оскільки для людей, що будуть бачити ці фото не важливо, в якому порядку вони туди потрапили). Після цього обираються 2 фотографії класу 9порядок знову ж таки не важливий). Залишається застосувати правило множення𝐶83∙𝐶62=8∙7∙61∙2∙3∙6∙51∙2=56∙15=560+280=840  

ЗНО 2019. У фінал пісенного конкурсу вийшло 4 солісти та 3 гурти. Порядковий номер виступу фіналістів визначають жеребкуванням. Скільки всього є варіантів послідовностей виступів фіналістів, якщо спочатку виступатимуть гурти, а після них – солісти. Уважайте, що кожен фіналіст виступатиме у фіналі лише один раз. Очевидно, що це задачка на правило множення. Для 3 гуртів кількість можливих варіантів розташування 3! = 6 Для 4 солістів: 4! = 246∙24=144  

Цікава (і корисна) властивість для сполучень 𝐶𝑛𝑘=𝐶𝑛𝑛−𝑘Наприклад, С10098=С100100−98=С1002=100∙991∙2=4950 В даній за задачі: кількість варіантів вибору хризантем С75=С72=7∙61∙2=21 ; кількість варіантів вибору півоній. С108=С102=10∙91∙2=45 І знову, правило множення: 21∙45=900+45=945 

ПРАКТИКУМ

Чи важливо тим, хто буде чергувати, під яким номером вони потрапили до списку. Звичайно – ні. Чергувати все одно доведеться. Отже, порядок не важливий

Використовуємо формулу сполучень (не сказано, що делегати «нумеруються». Тобто перший нічим не відрізняється від другого, а третій від першого)𝐶183=18∙17∙161∙2∙3=3∙256+16=3∙272=600+210+6=816 

Порядок розташування важливий. Очевидно, що числа 1357 та 1375 – різні. Тому необхідно використовувати формулу розміщень

Всі задані числа – прості. Дріб називається правильним, якщо чисельник менше знаменника. Для чисельника 2 маємо 8 дробів (в якості знаменника можна взяти будь-яке з восьми чисел 3, 5, 7. 11, 13, 17, 19, 23). Для чисельника 3 таких можливостей залишиться сім. І т.д. Причому кількості цих дробів треба додавати (а не множити), оскільки вибір дробів з одним чисельником не залежить від вибору дробів – з іншим.8+7+…+1=8+12∙8=9∙4=36 ЗНО 2008. Укажіть, скільки можна скласти правильних дробів, чисельниками і знаменниками яких є числа 2, 3, 4, 5, 6, 7, 8, 9. Відповідь: 28 

𝐶25=5∙41∙2=10 𝐴25=5∙4=20 𝐶2930=𝐶30−2930=𝐶130=30 𝑃4=1∙2∙3∙4=24