Що таке комбінаторика в математиці?
Комбiнаторика демонструє рiзнi способи поєднання елементiв.
У теорiї комбiнаторики використовується декiлька основних формул. Саме тому варто з’ясувати, з чим має справу комбiнаторика.
Уяви, що одного дня не знатимеш, що обрати з трьох футболок, двох пар штанiв та двох светрiв. Скiльки є рiзних способiв обрати один светр, одну футболку й одну пару штанiв? На подiбнi запитання i дає вiдповiдь комбiнаторика.
Щоб обчислити кiлькiсть окремих варiантiв поєднання елементiв, потрiбно помножити кiлькiсть можливих варiантiв. У цьому випадку йдеться про таке:
Приклад 1
На вечерi в ресторанi ти переглядаєш меню. Закуски тебе не зацiкавили, але десерт має дуже апетитний вигляд. Отже, ти з’їси одну головну страву i один десерт. У меню є три варiанти головних страв: сосиски, спагетi та пiца. Ти можеш вибрати один з трьох варiантiв десерту: браунi, солодкi булочки або торт. Скiльки рiзних комбiнацiй головної страви та десерту можна замовити?
Щоб розв’язати задачу, потрiбно помножити кiлькiсть страв у кожнiй категорiї: кiлькiсть головних страв множимо на кiлькiсть десертiв.
Отримуємо кiлькiсть можливих комбiнацiй . Це означає, що за наявностi трьох варiантiв головної страви i трьох варiантiв десерту iснує дев’ять рiзних способiв поєднати одну головну страву з одним десертом.
Правило
Комбiнаторика
Коли розв’язуєш задачi з комбiнаторики, множ кiлькiсть предметiв у кожнiй категорiї.
Помiркуй
Тобi потрiбно придумати код iз чотирьох цифр для мобiльного телефону. Скiльки варiантiв коду ти можеш придумати?
Щоб розрахувати кiлькiсть варiантiв коду, насамперед потрiбно з’ясувати, скiльки є варiантiв для кожної цифри. Iснує 10 варiантiв першої цифри коду — цифри вiд 0 до 9. Те саме стосується й другої, третьої та четвертої цифри коду. Отже, для кожної цифри доступно по 10 варiантiв.
Потiм потрiбно помножити кiлькiсть можливих варiантiв для кожної цифри коду. Отримаємо
Фактично iснує варiантiв коду з чотирьох цифр! Уяви, у скiлькох людей коди збiгаються.
Нас часто цiкавить кiлькiсть способiв, у якi можна виконувати рiзнi дiї. У комбiнаторицi використовується декiлька термiнiв, якi варто запам’ятати:
Теорiя
Важливi термiни
-
Впорядкована множина
-
означає, що має значення порядок. Наприклад, послiдовностi 1, 2, 3, 4 i 4, 3, 2, 1 вважаються двома рiзними результатами.
-
Невпорядкована множина
-
означає, що порядок не має значення. Наприклад, послiдовностi 1, 2, 3, 4 i 4, 3, 2, 1 — це той самий результат.
-
Iз замiною
-
означає, що той самий результат може статися неодноразово.
-
Без замiни
-
означає, що кожен результат можна отримати лише один раз.
Приклад 2
Мiкi Маус, Гуфi, Дональд Дак i Плуто — це чотири приятеля, якi збираються разом повечеряти, але забули сходити за продуктами. Отже, двоє з них муситимуть пiти до продуктового магазину. Те, хто саме пiде, — це невпорядкована множина (неважливо, вiдправимо ми Мiкi та Гуфi чи Гуфi та Мiкi). Оскiльки вiдправити потрiбно двох рiзних осiб, можна розглядати це як експеримент без замiни.
Увечерi настрiй у друзiв полiпшився, i всi четверо вирiшили пограти у Скребл. За результатами гри один iз друзiв буде переможцем, один посяде друге мiсце, один третє мiсце i один останнє мiсце. Ця послiдовнiсть являє собою впорядковану множину, оскiльки порядок тут грає роль: краще виграти, нiж програти. Це також множина без замiни, оскiльки та сама особа не може одночасно посiсти перше й третє мiсце. Впорядковану множину без замiни також називають перестановкою.
