У даній статті мова піде про особливому розділі математики під назвою комбінаторика. Формули, правила, приклади розв'язування задач – все це ви зможете знайти тут прочитавши статтю до самого кінця.
Отже, що ж це за розділ? Комбінаторика займається питанням підрахунку яких-небудь об'єктів. Але в даному випадку об'єктами виступають не сливи, груші або яблука, а щось інше. Комбінаторика допомагає нам знаходити ймовірність будь-якої події. Наприклад, при грі в карти – яка ймовірність того, що у супротивника є козирна карта? Або такий приклад – яка ймовірність того, що з мішка з двадцятьма кульками ви дістанете саме білий? Саме для такого роду завдань нам і потрібно знати хоча б основи даного розділу математики.
Комбінаторні конфігурації
Розглядаючи питання основних понять та формул комбінаторики, ми не можемо не приділити увагу комбінаторних конфігурацій. Вони використовуються не тільки для формулювання, але і для вирішення різних комбінаторних задач. Прикладами таких моделей є:
розміщення; перестановка; поєднання; композиція числа; розбиття числа. Про перших трьох ми поговоримо більш докладно далі, а ось композиції та розподіленню ми приділимо увага в даному розділі. Коли говорять про композиції певного числа (наприклад, а), то мають на увазі представлення числа а у вигляді впорядкованої суми якихось позитивних чисел. А розділення – це невпорядкована сума.
Розділи
Перш ніж ми перейдемо безпосередньо до формул комбінаторики та розгляду завдань, варто звернути увагу на те, що комбінаторика, як і інші розділи математики, має свої підрозділи. До них відносяться:
перечислительная; структурна; екстремальна; теорія Рамсея; імовірнісна; топологічна; инфинитарная. У першому випадку мова йде про исчисляющей комбінаториці, завдання розглядають перерахування або підрахунок різних конфігурацій, які утворені елементами множин. На дані множини, як правило, накладаються які-небудь обмеження (розрізнення, нерозрізненість, можливість повтору і так далі). А кількість цих конфігурацій підраховується за допомогою правила додавання або множення, про які ми поговоримо трохи пізніше. До структурної комбінаториці відносяться теорії графів і матроидов. Приклад екстремальної задачі комбінаторики – яка найбільша розмірність графа, який задовольняє таким властивостям В четвертому пункті ми згадали теорію Рамсея, яка вивчає у випадкових конфігураціях наявність регулярних структур. Імовірнісна комбінаторика здатна відповісти нам на питання, яка ймовірність того, що у заданої множини присутня певна властивість. Як неважко здогадатися, топологічна комбінаторика застосовує методи в топології. І, нарешті, сьомий пункт – инфинитарная комбінаторика вивчає застосування методів комбінаторики до нескінченною множиною.
Правило складання
Серед формул комбінаторики можна знайти і досить прості, з якими ми досить давно знайомі. Прикладом є правило суми. Припустимо, що нам дано дві дії (С і Е), якщо вони взаимоисключаеми, дія З здійснимо кількома способами (наприклад, а), а дія Е здійснимо b-способами, то виконати будь-яку з них (З або Е) можна а+b способами.
В теорії це зрозуміти достатньо важко, постараємося донести всю суть на простому прикладі. Візьмемо середню чисельність учнів одного класу - припустимо, це двадцять п'ять. Серед них п'ятнадцять дівчат та десять хлопців. Щодня в класі призначається один черговий. Скільки є способів призначити чергового по класу сьогодні? Рішення завдання досить просте, ми вдамося до правилом додавання. В тексті задачі не сказано, що черговими можуть бути тільки хлопчики або тільки дівчатка. Отже, ним може виявитися будь-яка з п'ятнадцяти дівчаток або будь-який з десяти хлопчиків. Застосовуючи правило суми, ми отримуємо досить простий приклад, з яким без праці впорається школяр початкових класів: 15 + 10. Підрахувавши, отримуємо відповідь: двадцять п'ять. Тобто існує всього двадцять п'ять способів призначити на сьогодні чергового класу.
Правило множення
До основних формул комбінаторики відноситься і правило множення. Почнемо з теорії. Припустимо, нам необхідно виконати кілька дій (а): перша дія виконується с1 способами, друге – с2 способами, третє – с3 способами і так далі до останнього а-дії, виконуваного са способами. Тоді всі ці дії (яких всього у нас а) можуть бути виконані N способами. Як вирахувати невідому N? В цьому нам допоможе формула: N = с1 * с2 * 3 ** са.
Знову ж таки, в теорії нічого не зрозуміло, переходимо до розгляду простого прикладу застосування правила множення. Візьмемо той же клас з двадцяти п'яти чоловік, в якому навчається п'ятнадцять дівчат та десять хлопців. Тільки на цей раз нам необхідно вибрати двох чергових. Ними можуть бути, як тільки хлопчики або дівчатка, так і хлопчик з дівчинкою. Переходимо до елементарного вирішення завдання. Вибираємо першого чергового, як ми вирішили у минулому пункті, у нас виходить двадцять п'ять можливих варіантів. Другим черговим може бути будь-який з решти людей. У нас було двадцять п'ять учнів, одного ми обрали, значить другим черговим може бути будь-який з решти двадцяти чотирьох чоловік. Нарешті, застосовуємо правило множення і отримуємо, що двох чергових можна обрати шістьма сотнями способів. Ми дане число отримали множенням двадцяти п'яти і двадцяти чотирьох.
Перестановка
Зараз ми розглянемо ще одну формулу комбінаторики. В даному розділі статті ми поговоримо про перестановки. Розглянути проблему пропонуємо одразу ж на прикладі. Візьмемо більярдні кулі у нас їх n-ое кількість. Нам потрібно підрахувати, скільки є варіантів розставити їх в ряд, тобто скласти впорядкований набір. Почнемо, якщо у нас немає куль, то і варіантів розстановки у нас так само нуль. А якщо у нас куля один, то і розстановка теж одна (математично це можна записати наступним чином: Р1 = 1). Дві кулі можна розставити двома різними способами: 12 і 21. Отже, Р2 = 2. Три кулі можна розставити вже шістьма способами (Р3=6): 123; 132; 213; 231; 321; 312. А якщо таких куль не три, а десять або п'ятнадцять? Перераховувати всі можливі варіанти дуже довго, тоді нам на допомогу приходить комбінаторика. Формула перестановки допоможе нам знайти відповідь на питання, що цікавить нас. Pn = n *P (n-1). Якщо спробувати спростити формулу, отримуємо: Pn = n* (n - 1) ** 2 * 1. А це і є добуток перших натуральних чисел. Таке число називається факториалом, а позначається як n!
Розглянемо задачу. Вожатий щоранку вибудовує свій загін у шеренгу (двадцять осіб). В загоні є три кращих друга – Костя, Саша і Льоша. Яка ймовірність того, що вони будуть стояти поруч? Щоб знайти відповідь на питання, потрібно ймовірність «хорошого» результату поділити на загальну кількість випадків. Загальне число перестановок становить 20! = 25 квінтильйонів. Як порахувати кількість «хороших» результатів? Припустимо, що Костя, Саші і Льоша – це один надлюдина. Тоді ми маємо всього вісімнадцять суб'єктів. Число перестановок в даному випадку дорівнює 18 = 65 квадрильйонів. При всьому цьому, Костя, Саша і Льоша можуть довільно переміщатися між собою у своїй неподільної трійці, а це ще 3! = 6 варіантів. Значить все «хороших» розстановок у нас 18! * 3! Нам залишається тільки знайти шукану ймовірність: (18! * 3!) /20! Що дорівнює приблизно 0016. Якщо перевести у відсотки, то це виходить всього 16%.
Розміщення
Зараз ми розглянемо ще одну дуже важливу і необхідну формулу комбінаторики. Розміщення – це наш наступний питання, який пропонуємо вам розглянути в цьому розділі статті. Ми йдемо на ускладнення. Припустимо, що ми хочемо розглянути можливі перестановки, тільки не з усієї множини (n), а з меншого (m). Тобто ми розглядаємо перестановки з n по m предметів. Основні формули комбінаторики варто не просто заучувати, а розуміти їх. Навіть незважаючи на те, що вони ускладнюються, так як у нас не один параметр, а два. Припустимо, що m = 1 і = 1 m = 2 то А = n * (n - 1). Якщо далі спрощувати формулу і перейти на запис за допомогою факториалов, то вийде цілком лаконічна формула: А = n! /(n - m)!
Поєднання
Ми розглянули практично всі основні формули комбінаторики з прикладами. Тепер перейдемо до заключного етапу розгляду базового курсу комбінаторики – знайомство з поєднанням. Зараз ми будемо вибирати m предметів з наявних у нас n, при цьому всьому ми будемо вибирати усіма можливими способами. Чому ж тоді це відрізняється від розміщення? Ми не будемо враховувати порядок. Цей невпорядкований набір і буде поєднанням.
Відразу введемо позначення: С. Беремо розміщення m кульок з n. Ми перестаємо звертати увагу на порядок і отримуємо повторювані поєднання. Щоб отримати число сполучень нам треба поділити число розміщень на m! (m факторіал). Тобто С = А /m! Таким чином, способів вибрати n куль трошки, дорівнює приблизно стільки, скільки вибрати майже все. Цьому є логічне вираз: вибрати трошки все одно, що викинути майже все. Ще в даному пункті важливо згадати і те, що максимальне число поєднань можна досягти при спробі вибрати половину предметів.
Як вибрати формулу для рішення завдання?
Ми докладно розглянули основні формули комбінаторики: розміщення, перестановка і поєднання. Тепер наше завдання – полегшити вибір необхідної формули для розв'язання задачі з комбінаторики. Можна скористатися наступною досить простою схемою:
Задайте собі питання: порядок розміщення елементів враховується в тексті задачі? Якщо відповіді немає, то скористайтеся формулою поєднання (С = n! /(m! * (n - m)!)). Якщо відповіді немає, то необхідно відповісти на ще одне питання: чи всі елементи входять у комбінацію? Якщо відповідь так, то скористайтеся формулою перестановки (Р = n!). Якщо відповіді немає, то скористайтеся формулою розміщення (А = n! /(n - m)!). Приклад
Ми розглянули елементи комбінаторики, формули та деякі інші питання. Тепер перейдемо до розгляду реальної задачі. Уявіть, що перед вами лежать ківі, апельсин і банан.
Питання перше: скількома способами їх можна переставити? Для цього скористаємося формулою перестановок: Р = 3! = 6 способів. Питання друге: скількома способами можна вибрати один фрукт? Це очевидно, у нас всього три варіанти – вибрати ківі, апельсин або банан, але застосуємо формулу сполучень: = 3! /(2! * 1!) = 3. Питання третє: скількома способами можна вибрати два фрукта? Які є у нас взагалі варіанти? Ківі і апельсин; ківі і банан, апельсин і банан. То є три варіанти, але це легко перевірити за допомогою формули поєднання: З = 3! /(1! * 2!) = 3 Питання четверте: скількома способами можна вибрати три фрукта? Як видно, вибрати три фрукта можна одним-єдиним способом: взяти ківі, апельсин і банан. З = 3! /(0! * 3!) = 1. Питання п'яте: скількома способами можна вибрати хоча б один фрукт? Ця умова передбачає, що ми можемо взяти один, два або всі три фрукта. Отже, ми складаємо С1 + С2 + С3 =3 + 3 + 1 = 7. Тобто у нас є сім способів узяти зі столу хоча б один фрукт.
