Поговоримо про один з розділів теорії ймовірності - комбінаторики.
Комбінаторика - гілка математики, що вивчає комбінації та перестановки предметів. Ще комбінаторики можна розуміти як перебір можливих варіантів. Комбінаторика виникла в 17 столітті. Довгий час вона лежала поза основним руслом розвитку математики.
Із завданнями, в яких доводилося вибирати ті чи інші предмети, розташовувати їх в певному порядку і відшукувати серед різних розташувань найкращі, люди зіткнулися ще в доісторичну епоху, вибираючи найкраще положення мисливців під час полювання, воїнів - під час битви, інструментів - під час роботи .
Комбінаторні навички виявилися корисними і в години дозвілля. Не можна точно сказати, коли поряд зі змаганнями в бігу, метанні диска, стрибках з'явилися гри, які вимагали, в першу чергу, вміння розраховувати, складати плани і спростовувати плани противника.
Згодом з'явилися різні ігри (нарди, карти, шашки, шахи і т.д.). У кожній з цих ігор доводилося розглядати різні поєднання фігур, і вигравав той, хто їх краще вивчив, знав виграшні комбінації і вмів уникати програшних. Не тільки азартні ігри давали їжу для комбінаторних роздумів математиків. Ще з давніх-давен дипломати, прагнучи до таємниці листування, винаходили складні шифри, а секретні служби інших держав намагалися ці шифри розгадати. Стали застосовувати шифри, засновані на комбінаторних принципах, наприклад, на різних перестановках літер, заміни букв з використанням ключових слів і т.д.
Комбінаторика як наука почала розвиватися в 18 столітті паралельно з виникненням теорії ймовірностей, так як для вирішення імовірнісних задач необхідно було підрахувати число різних комбінацій елементів. Перші наукові дослідження з комбінаторики належать італійським вченим Дж.Кардано, Н.Тарталье (1499-1557), Г. Галілею (1564-1642) і французс- ким вченим Б. Паскаля (1623-1662) і П.Ферма.
Отже, твір всіх натуральних чисел від 1 до n включно називають n-факторіалом і пишуть: n! = 1 2 3 ... (n-1) n
В комбінаториці вирішуються завдання, пов'язані з розглядом множин та складанням різних комбінацій з елементів цих множин. Залежно від правил складання можна виділити три типи комбінацій: перестановки, розміщення, поєднання.
Будемо надалі оперувати тільки з множинами, що містять кінцеве число елементів. На нескінченні безлічі все наведені нижче правила та формули не поширюються.
Теорема 2.1. Нехай дано непересічні кінцеві безлічі. Тоді потужність об'єднання цих множин дорівнює сумі потужностей даних множин:
Доказ цієї теореми очевидно. Але для нас представляє інтерес інша інтерпретація цієї теореми, яку ми сформулюємо для двох множин.
Якщо певний елемент можна вибрати способами, а елемент - способами, причому будь-який спосіб вибору елемента відрізняється від будь-якого способу вибору елемента, то вибір "або" можна зробити способами. Це правило називається правилом суми.
Нехай дано непересічні кінцеві безлічі. Позначимо число елементів в цих множинах (їх потужності). Розглянемо декартовій твір цих множин. Нагадаємо, що елементами цього твору будуть вектори (кортежі) довжини виду.
Теорема 2.2. Число елементів в декартовом творі множин дорівнює добутку потужностей цих множин:
Як і в попередньому випадку, сформулюємо цю теорему спрощеним чином для двох множин. Якщо елемент можна вибрати способами, а елемент - способами, причому будь-який спосіб вибору елемента відрізняється від будь-якого способу вибору елемента, то вибір "і" (тобто, пари) можна зробити способами. Це правило називається правилом твори, або множення.
Обидва сформульованих правила вірні для будь-якого кінцевого числа кінцевих множин, і, у відповідній формі, називаються узагальненими.
а) В деякій середній школі є три п'ятих класи, в яких навчаються відповідно 28, 31 і 26 учнів. Потрібно одного з них вибрати для участі в раді школи. Скількома способами можна зробити вибір?
За правилом суми отримуємо.
б) У секції фігурного катання займаються 14 хлопчиків і 18 дівчаток. Скількома різними способами з дітей, що займаються в секції, можна утворити спортивні пари.
За правилом твори отримуємо.
Визначення. Будь-вектор довжини, складений з елементів елементного безлічі, в якому всі елементи різні, називається розміщенням без повторень по елементів з. Число всіх розміщень без повторень по елементів з позначається і так само.
Приклад 2. Придбано різних 12 книг. На полиці можна поставити в ряд рівно 6 книг. Скількома різними способами можна це зробити?
Будемо вважати різними не тільки ті випадки, коли беруться різні книги, але і коли вони по-різному розставлені на полиці (в різному порядку). Тоді мова йде про перестановки по 6 з 12. Отримуємо:.
Розглянемо істотно інший випадок, а саме коли елементи безлічі в векторах можуть повторюватися.
Визначення. Будь-вектор довжини, складений з елементів елементного безлічі, що складається з елементів, в якому всі елементи різні, називається розміщенням з повтореннями по елементів з. Число всіх розміщень з повтореннями по елементів з позначається і так само.
Приклад 3. Скільки різних комбінацій може вийти при одночасному киданні трьох гральних кісток?
Кожна гральна кістка являє собою кубик, на гранях якого нанесено від одного до 6 очок. При кожному киданні ми будемо отримувати набори виду, де - кількість очок, що випали на відповідній кістки. Мова йде про перестановки з повтореннями по 3 елементи з 6. Отримуємо:.
Зауваження. Очевидно, що розміщення без повторень є окремим випадком розміщень з повтореннями.
Визначення. Будь-вектор довжини, складений з елементів елементного безлічі, в якому всі елементи різні, називається перестановкою без повторень з елементів. Число всіх перестановок без повторень з елементів позначається і так само.
З визначення і формули видно, що перестановки без повторень є окремий випадок розміщень без повторень, за умови.
Приклад 4. Скількома різними способами можна розставити на полиці 10 різних книг?
Тут, на відміну від прикладу 2, значення має тільки порядок розставляються книг. Тому мова йде про перестановки з 10 елементів. Отримуємо:.
Розглянемо випадок, коли елементи безлічі повторюються по декілька разів. Для визначеності нехай 1-й елемент повторюється раз, 2-й елемент - раз і так далі. Тоді вектори довжини, утворені з елементів даної множини називаються перестановками з елементів з повтореннями. Число таких перестановок позначається і так само.
Поклавши в останній формулі, отримаємо формулу для перестановок без повторень.
Приклад 5. Скільки різних шестизначних чисел можуть бути записано за допомогою цифр 1, 2, 2, 2, 3, 3?
Є набір з шести цифр, в якому цифра 2 повторюється тричі і цифра 3 - двічі. Отримані числа будуть являти собою перестановки з повтореннями з 6 елементів. Отримуємо:.
Перш за все, відзначимо одна істотна відмінність перестановок від розміщень. Якщо в розміщених вектори розрізняються і за складом елементів, і по їх розташуванню (порядку) в наборі, то в перестановках вектори розрізняються тільки по розташуванню елементів. Природно розглянути випадок, коли вектори, навпаки, будуть відрізнятися тільки за складом елементів.
Визначення. Будь-які різні вектори довжини, складені з елементів елементного безлічі, що розрізняються між собою по набору елементів, але не по їх розташуванню в наборі, називаються сполученнями по елементів з.
Якщо всі елементи, що утворюють поєднання, різні, то їх називають поєднанням без повторень. Позначення всіх сполучень без повторень. Формула для обчислення. Якщо деякі (або всі) елементи, що утворюють поєднання, можуть повторюватися, то їх називають поєднаннями повтореннями. Позначення всіх сполучень без повторень. Формула для обчислення. Запам'ятовувати останню формулу немає необхідності.
Зауваження 1. Сполучення є окремим випадком розміщень. Різниця між поєднаннями і розміщеннями з визначення неочевидна, але на конкретних прикладах її легко бачити. Так, наприклад, вектори і є різними розміщеннями, але означають одне і те ж поєднання.
Зауваження 2. Для сполучень без повторень обов'язково вимога, причому в разі рівності отримаємо природний результат. Але для поєднань з повтореннями це вимога необов'язково, як буде видно з наведеного нижче прикладу.
а) У відділі працюють 10 співробітників. Потрібно відібрати трьох з них для того, щоб направити у відрядження. Скількома способами можна це зробити?
Оскільки має значення тільки те, які саме співробітники відібрані, то мова йде про поєднання без повторень по 3 елементи з 10. Отримуємо:
б) У квітковому магазині є в продажу 5 різних видів квітів. Покупцеві потрібно скласти букет з 7 кольорів. Скількома способами можна це зробити?
Будемо вважати різними ті букети, які відрізняються один від одного по підбору кольорів. Оскільки квіти в букеті можуть повторюватися, то мова йде про поєднання з повтореннями по 7 елементів з 5. Тоді отримаємо.
Одним з найбільш відомих прикладів використання комбінаторних формул є так званий біном Ньютона. У загальному вигляді формула бінома (двочлена) Ньютона виглядає так:
З окремими випадками застосування цієї формули (для випадків і) стикаються ще в школі при вивченні формул скороченого множення:
На практиці для зручності застосування бинома Ньютона застосовують так званий трикутник Паскаля, який містить числові коефіцієнти полінома в правій частині формули: