UK 
EnglishТипова
Polski🔢 Комбінаторика та Підрахунок
Візуалізуйте перестановки, комбінації та принцип множення — дивіться, як будуються правила підрахунку.
Про принципи підрахунку в комбінаториці
Комбінаторика — це розділ математики, що вивчає підрахунок розташувань і виборів. Дві фундаментальні операції — перестановки (упорядковані розташування r елементів, обраних з n, обчислюються як P(n,r) = n!/(n−r)!) і комбінації (невпорядковані вибірки, обчислюються як C(n,r) = n!/(r!(n−r)!)). Відношення P/C = r! точно показує, скільки впорядкувань відповідає кожному вибору. Ці формули застосовуються в теорії ймовірностей, криптографії, генетиці (підрахунок можливих послідовностей ДНК) та аналізі алгоритмів (підрахунок порівнянь при сортуванні).
Цей інтерактивний інструмент дозволяє змінювати n (загальна кількість елементів) і r (кількість обраних), перемикатися між режимами перестановки, комбінації, трикутника Паскаля та включень-виключень, а також читати точні значення. Стовпчикова діаграма внизу порівнює P(n,r) і C(n,r) для всіх значень r одночасно, показуючи вибухове факторіальне зростання, через яке великі комбінаторні простори стають обчислювально нездійсненними.
Часті запитання
У чому різниця між перестановкою та комбінацією?
У перестановці порядок важливий, у комбінації — ні. Розташування 3 літер, обраних з {A, B, C, D}, дає P(4,3) = 24 різні послідовності (ABC і BAC — різні). Вибір 3 літер з того самого набору дає C(4,3) = 4 різні групи (ABC і BAC — та сама група). Відношення P/C = r! = 6 показує, скільки впорядкувань має кожна група.
Чому трикутник Паскаля дає біноміальні коефіцієнти?
Трикутник Паскаля побудований так, що кожне число дорівнює сумі двох чисел над ним: C(n,k) = C(n−1,k−1) + C(n−1,k). Ця рекурентність відображає комбінаторну тотожність, що вибір k елементів з n еквівалентний включенню або виключенню конкретного елемента. Рядок n трикутника містить C(n,0), C(n,1), …, C(n,n) — саме ці коефіцієнти є в біноміальному розкладі (x+y)^n.
Що таке принцип включень-виключень?
Принцип включень-виключень підраховує розмір об'єднання множин, почергово додаючи й віднімаючи перетини: |A∪B| = |A| + |B| − |A∩B|. Для трьох множин він розширюється до |A∪B∪C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. Він використовується в теорії ймовірностей (об'єднання подій), теорії графів (підрахунок дерангементів) та аналізі алгоритмів (підрахунок рядків, що задовольняють кілька обмежень).
Наскільки швидко зростає n!?
Факторіальне зростання гіперекспоненційне: 10! = 3 628 800; 20! ≈ 2,4 × 10¹⁸; 52! ≈ 8 × 10⁶⁷ (кількість способів перетасувати колоду карт). Наближення Стірлінга n! ≈ √(2πn)·(n/e)^n показує, що факторіальне зростання перевищує будь-яку фіксовану експоненту 2^n при великих n. Саме тому повний перебір усіх перестановок стає нездійсненним навіть при помірних n.
Що таке біноміальна теорема?
Біноміальна теорема стверджує, що (x+y)^n = Σ_{k=0}^{n} C(n,k) x^(n−k) y^k. Коефіцієнт кожного доданка C(n,k) підраховує кількість способів вибрати k множників y з n множників (x+y). Підстановка x = y = 1 дає 2^n = Σ C(n,k), показуючи, що загальна кількість підмножин множини з n елементів дорівнює 2^n. Підстановка x = 1, y = −1 дає знакозмінну суму Σ (−1)^k C(n,k) = 0.
Що таке дерангементи і як їх рахують?
Дерангемент — це перестановка без жодного елемента на початковій позиції — наприклад, перестановка {1,2,3} так, щоб 1 не була на позиції 1, 2 не була на позиції 2, і 3 не була на позиції 3. Кількість дерангементів D(n) = n! × Σ_{k=0}^{n} (−1)^k / k!, що за включенням-виключенням дорівнює найближчому цілому до n!/e. При великих n приблизно 1/e ≈ 36,8% усіх перестановок є дерангементами.
Що таке техніка «зірки й розділювачі»?
«Зірки й розділювачі» підраховує кількість способів розподілити n однакових об'єктів по k різних кошиках (дозволяючи порожні кошики): C(n+k−1, k−1). Наприклад, 7 однакових цукерок для 3 дітей = C(9,2) = 36 способів. Якщо порожні кошики не дозволені (кожна дитина повинна отримати хоча б одну цукерку), відповідь — C(n−1, k−1) = C(6,2) = 15. Ця техніка лежить в основі твірних функцій та вилучення коефіцієнтів многочленів.
Як комбінаторика лежить в основі теорії ймовірностей?
Класична ймовірність визначає ймовірність події як (сприятливі результати) / (загальна кількість рівноймовірних результатів). І чисельник, і знаменник зазвичай обчислюються за допомогою перестановок і комбінацій. Наприклад, ймовірність того, що покерна рука з 5 карт — флеш, дорівнює C(13,5) × 4 / C(52,5) ≈ 0,00198, бо ви обираєте 5 рангів із 13 в одній з 4 мастей, з усіх можливих рук по 5 карт.
Чому розфарбування трикутника Паскаля за модулем m розкриває візерунки Серпінського?
Розфарбування елементів трикутника Паскаля за C(n,k) mod p (для простого p) дає фрактал трикутника Серпінського при p = 2. Це випливає з теореми Лукаса: C(n,k) mod p ≡ добутку C(nᵢ, kᵢ) mod p для кожного розряду в поданнях n і k за основою p. Елементи дорівнюють нулю за модулем p щоразу, коли будь-який розряд k перевищує відповідний розряд n за основою p, створюючи самоподібні «дірки» на кожному масштабі.
Як комбінації використовуються в генетиці?
У генетиці C(n,k) підраховує кількість способів, якими k мутацій можуть відбутися в геномі з n пар основ — це критично для оцінки ймовірності конкретних онкогенних мутацій. Закон Харді–Вайнберга використовує біноміальні коефіцієнти для прогнозування частот генотипів у популяції, а комбінаторний підрахунок лежить в основі обчислення кількості можливих структур антитіл, які може виробити імунна система (оцінюється у понад 10¹⁸ різних конфігурацій).