Комбінаторика
Комбінаторика одна із розділів математики, вивчає завдання розташування, поєднання, вибору об'єктів у різних ситуаціях (умовах).
Іноді обговорення "перестановок та поєднань" починається з питання, подібного до наступного:
Скількими способами може одягнутися людина, комбінуючи три сорочки, дві краватки та дві пари черевиків?
Нехай перша координата вказує варіант вибору сорочки, друга – краватка, а третя – черевик.
(1,1,1) (1,1,2) (1,2,1) (1,2,2) для комбінації з першою сорочкою
(2,1,1) (2,1,2) (2,2,1) (2,2,2) для комбінації з другою сорочкою
(3,1,1) (3,1,2) (3,2,1) (3,2,2) для комбінації з третьою сорочкою
Ця сукупність є безліччю всіх упорядкованих пар.
Тепер зрозуміло, що правильною відповіддю служить число 3 ∙ 2 ∙ 2 = 12.
Отже, сформулюємо загальне твердження:
Основне правило комбінаторики
Нехай необхідно кілька разів зробити вибір. Існує m1 варіантів при першому виборі, m2 – при другому, m3 – при третьому і т.д.
Якщо щоразу вибір проводиться без будь-яких обмежень, тоді загальна кількість можливостей для всієї послідовності виборів дорівнює:
Тепер познайомимося з основними стандартними методами обчислень, які використовуються під час вирішення комбінаторних завдань.
Міркування наводимо на основі наступного прикладу:
Нехай урна міститьmрізних куль із номерами від 1 доm. З неї вилучаютьсяnкуль за дотримання деяких умов спосіб вилучення. Для кожної моделі обчислюються кількості всіх можливих наслідків.
1. Розміщення (або впорядкований вибір)
1.1 Число розміщень із поверненням
Кулі витягуються навмання одна за одною, причому коженвийнята куля повертається назад в урну перш, ніж буде вилучено наступний. При цьому записуються номери куль у порядку їх появи.
Таким чином, ми маємо справу з упорядкованими наборами (a1.an), у яких кожнеajможе набувати будь-якого значення від 1 доm.
Основне правило відразу призводить до відповідіm nдля повного числа наслідків.
1.2 Число розміщень без повернення
Кулі витягуються навмання один за одним, проте в даній моделі вони не повертаються назад до урни. Ми знову маємо справу з упорядкованими наборами (a1.an), але вже з обмеженням, що в них всі різні. Звичайно, повинна виконуватися нерівність n менше або m. Основне правило безпосередньо не застосовується. Тим не менш, зважаючи на те, що на кожному кроці число куль в урні стає на одну менше, можемо записати:
Ця модель має важливий окремий випадок - модель перестановок.
1.2 a. Перестановка зmпомітних куль
Розглянемо модель 1.2 приm=n.
Тоді всіmкуль витягуються одна одною без повернень. Результатом вибору є набірmзанумерованих куль, розставлених в деякому порядку. Повна кількість можливостей збігається з числом всіх розташування елементів множини. Це число називаєтьсяфакторіаломвідmі позначається
2. Поєднання (або невпорядкований вибір)
Модель передбачає, що порядок номерів витягнутих кульок не фіксується. На відміну від моделі розміщень, набори, що відрізняються лише порядком прямування елементів, вважаються однаковими.
2.1 Число поєднань без повернення
Отже, вийняті кулі не повертаються назад до скриньки, а також не фіксується порядок їх номерів упроцесі вилучення.
Інакше кажучи, можна уявити, що цеnкуль виймаються відразу за одне витяг.
Отже, ми маємо справу з вибором довільного підмножини розміруnз множини розміруm.
З попередніх міркувань зрозуміло, що впорядкована вибірка розміруnпороджуєn!невпорядкованих, за кожною з яких можна однозначно відновити вихідну.
З обговорення моделі 1.2 відомо, що кількість послідовних наборів розміруnдорівнює(m)n.
Позначимо заxпотрібне число результатів (підмножин розміруn). Проведені вище міркування показують, що
Звідси отримуємо відповідь:
Якщо помножити чисельник та знаменник на(m-n)!, отримаємо:
(*)
Вираз (*) називаєтьсябіноміальним коефіцієнтомі відіграє важливу роль у теорії ймовірностей.
Зауважте, що вірна тотожність
2.1.a. Перестановка зmкуль, невиразних усередині груп
Припустимо,що ми маємоm1куль кольору номер 1,m2куль кольору номер 2, .mrкуль кольору номерr. Кольори різняться, а кулі одного кольору – ні.
Звичайно,m1+m2+. +mr=m. Скільки існує відмінних перестановок таких куль?
Використовуючи міркування із 1.2.a. для кожної первісної перестановки без розрізнення куль одного кольору через основне правило існує
нових способів розміщення з урахуванням нумерації.
Міркування аналогічні проведеним для моделі 2.1 показують, що кількість ненумерованих перестановок дорівнює приватному:
Число називаєтьсямультиноміальним(абополіноміальним) коефіцієнтів. Колиr=2, коефіцієнт зводиться добіноміальному.
2.2 Число поєднань із поверненням
З урни витягуються один за одним n куль, кожна вийнята куля повертається назад перш, ніж буде вилучено наступний.
У цьому (можливо, повторювані) номери всіх вийнятих куль реєструються як невпорядкованого набору (групи), тобто. без звернення уваги порядок їх появи.
Література
К.Л. Чжун, Ф. АїтСахліа. Елементарний курс теорії імовірностей. Стохастичні процеси та фінансова математика. Переклад з англійської М.Б. Лагутіна, М: БІНОМ. Лабораторія знань, 2007