Комбінаторика та підрахунок: Математика кількості

Множинне правило: основа будь-якої лічилки

Майже кожна формула лічби в математиці базується на одній ідеї, що повторюється: якщо зробити перший вибір у a способів, а потім незалежний другий – у b способів, то весь ланцюг виборів можна здійснити у a·b способів. П’ятидісне дегустаційне меню з 4 стравами-замінниками, 3 супами, 5 основними стравами, 2 десертами та 3 напоями має 4·3·5·2·3 = 360 можливих варіантів – не потрібно записувати 360 меню, щоб це зрозуміти. Це множинне правило, а факторіали, перестановки та комбінації – це лише скорочення для застосування його багато разів без необхідності вести облік.

Перестановки: коли порядок має значення

Перестановка – це впорядковане розташування. Розміщення всіх n різних об'єктів у ряд має n варіантів для першого слоту, n-1 для другого (один вже використаний), n-2 для третього і так далі до 1 — це добуток, який називається факторіалом числа n, позначається як n! Розміщення лише k з n об'єктів припиняє цей добуток на k кроків раніше:

n! = n · (n-1) · (n-2) · … · 2 · 1        (0! = 1, by convention)

P(n,k) = n! / (n-k)!   — ordered arrangements of k items chosen from n

example: 3 medals awarded to 8 sprinters
P(8,3) = 8! / 5! = 8 · 7 · 6 = 336 possible podiums

Комбінації: коли порядок не має значення

Комбінація – це безпорядкова вибірка — комітет, рука карт, підмножисті. Будь-яка група з k елементів може бути впорядкована в k! різних порядків, тому якщо порахувати впорядковані розміщення P(n,k) і поділити їх на k! повторюваних порядків, ми отримаємо кількість унікальних груп:

C(n,k) = P(n,k) / k! = n! / (k! · (n-k)!) — читається як "n комбінації з k"

Наприклад: рука в 5 карт з колоди з 52 карт C(52,5) = 52! / (5! · 47!) = 2 598 960 можливих рук C(n,k) також називається біноміальним коефіцієнтом, оскільки це точно коефіцієнт x^k в розкладі (1+x)^n — факт, відомий як біноміальна теорема. Розкладаючи всі C(n,k) для фіксованого n у ряд і розміщуючи кожен n як новий рядок, отримуємо трикутник Паскаля: кожне значення є сумою двох значень вище нього, оскільки при виборі k елементів з n ми або включаємо один конкретний елемент (залишаючи C(n-1,k-1) способів заповнити решту), або не включаємо його (залишаючи C(n-1,k) способів).

C(n,k) = P(n,k) / k! = n! / (k! · (n-k)!)   — read "n choose k"

example: a 5-card poker hand from a 52-card deck
C(52,5) = 52! / (5! · 47!) = 2,598,960 possible hands

Повторення та принцип папуги

Постійно виникають дві розширені версії. Якщо варіанти можуть повторюватися – наприклад, 4-значний PIN-код або кодон ДНК з 3 основ {A,C,G,T} – то застосовується принцип множення без ділення: n^k загальна кількість послідовностей (10 000 PIN-ів, 4³ = 64 кодонів). Якщо ж ви розподіляєте ідентичні предмети в окремі контейнери (наприклад, 10 ідентичних наклейок серед 4 дітей), то підрахунок здійснюється за допомогою комбінації «зірки та перегородки», C(n+k-1, k-1), оскільки ви насправді обираєте, де розмістити k-1 роздільників серед n+k-1 слотів.

Принцип папуги – улюблений доведення існування в комбінаториці: якщо ви розміщуєте більше ніж n предметів у n контейнерів, то принаймні один контейнер міститиме два або більше предметів – не потрібна формула, достатньо порівняти суми. Це звучить тривіально і доводить дивовижно глибокі результати, від гарантування того, що двоє людей у Лондоні мають спільний день народження плюс година, до обмеження алгоритмів стиснення: неможливо без втрат стиснути кожен можливий файл, оскільки існує більше вхідних файлів, ніж коротших вихідних файлів для їх відображення.

Де насправді важлива кількість

Ці формули є математичною основою для обчислення ймовірностей (ймовірність зазвичай дорівнює кількості сприятливих результатів, поділеній на загальну кількість), оцінок простору ключів шифрування, меж зіткнень хеш-функцій та аналізу складності алгоритмів, де підрахунок можливої кількості входів або станів обмежує швидкість пошуку методом грубої сили. У симуляції на цій сторінці ви можете змінювати n і k та спостерігати, як кількість швидко зростає – факторіали ростуть настільки швидко, що C(60,30), задача про комітет помірних розмірів, вже перевищує кількість атомів у людському тілі.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Combinatorics & Counting і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.