Калькулятор перестановок та комбінацій

Використовуйте перестановки, коли порядок або розташування обраних елементів має значення:

• розподіл призових місць (1-ше, 2-ге, 3-тє місце)
• розстановка книг на полиці
• створення паролів або PIN-кодів
• розсаджування гостей
• телефонні номери

Використовуйте комбінації, коли ви просто вибираєте підмножину і порядок не важливий:

• вибір учасників команди
• вибір лотерейних номерів
• замовлення страв у меню
• формування комітетів або груп

Простий тест: якщо зміна місцями двох обраних елементів дає новий результат — використовуйте перестановки; якщо результат залишається тим самим — комбінації.

Лотерейні номери чудово це ілюструють: у розіграші Mega Millions вибирають 5 номерів із 70 плюс 1 із 25: C(70,5) × 25 = 302,575,350 можливих квитків. Якби порядок мав значення, кількість варіантів становила б P(70,5) × 25 = 36,309,042,000 — у 120 разів більше.

Базові перестановки (розміщення): P(n,r) = n!/(n-r)!. P(10,3) = 10!/7! = 10×9×8 = 720.

Базові комбінації: C(n,r) = n!/[r!(n-r)!]. C(10,3) = 10!/(3!×7!) = 720/6 = 120.

З дозволеними повтореннями: перестановки = n^r (наприклад, 4-значний PIN-код із цифр 0–9 має 10⁴ = 10,000 комбінацій).

Комбінації з повтореннями: C(n+r-1, r) — вибір 3 кульок морозива з 5 смаків з можливістю повторення дає C(7,3) = 35.

Для великих чисел використовуйте мультиплікативну формулу зі скороченням, щоб уникнути розрахунку гігантських факторіалів: C(52,5) = (52×51×50×49×48)/(5×4×3×2×1) = 2,598,960 — кількість можливих 5-карткових комбінацій у покері.

Безпека паролів: 8-значний пароль із великих, малих літер, цифр та 10 спецсимволів (72 варіанти символів) має 72⁸ = 722 трильйони перестановок із повтореннями — для зламу методом перебору знадобиться близько 22,800 років при швидкості 1 мільярд спроб на секунду. Додавання лише 2 символів (10-значний пароль) збільшує кількість варіантів до 3.7 квадрильйона — зламати його стає в 5,140 разів складніше.

• У генетиці кількість варіантів вибору 23 пар хромосом із 46 хромосом батьків становить C(46,23) ≈ 8.2 мільярда, що пояснює генетичне різноманіття.
• У контролі якості вибір 5 виробів із партії в 100 штук для тестування дає C(100,5) = 75,287,520 можливих вибірок.
• У турнірних сітках кількість можливих варіантів заповнення сітки NCAA March Madness дорівнює 2⁶³ ≈ 9.2 квінтильйона — саме тому ще нікому не вдалося вгадати її бездоганно.

Перестановка — це впорядковане розташування елементів, тоді як комбінація — це вибірка без урахування порядку. Уся суть різниці полягає виключно в порядку елементів.

Якщо ви берете літери A, B і C, то варіанти ABC і CAB — це дві різні перестановки, але одна й та сама комбінація, оскільки для комбінації важливо лише те, які елементи обрано, а не їхня послідовність. Як зазначає Encyclopaedia Britannica, комбінаторика — це розділ математики, присвячений підрахунку таких розміщень і вибірок.

Швидкий тест: запитайте себе, чи зміниться результат, якщо поміняти два обрані елементи місцями. Розподіл золотої, срібної та бронзової медалей зміниться, якщо поміняти двох бігунів місцями, тому порядок має значення й застосовуються перестановки. Вибір трьох інгредієнтів для піци не зміниться, якщо переставити їх місцями, тому використовуються комбінації.

Формула перестановок має вигляд nPr = n! / (n − r)!, а формула комбінацій — nCr = n! / [r! × (n − r)!], де n! (факторіал числа n) є добутком усіх цілих чисел від 1 до n.

Щоб знайти P(10,3), обчисліть 10! / 7!, що спрощується до 10 × 9 × 8 = 720. Щоб знайти C(10,3), поділіть цей результат на 3! = 6 і отримайте 120. Самі факторіали зростають дуже швидко: 5! = 120, а 10! = 3,628,800.

Wolfram MathWorld визначає біноміальний коефіцієнт C(n,r) саме так. Оскільки nCr виключає r! варіантів порядку, які перестановки враховують окремо, nCr завжди менше або дорівнює nPr для однакових значень n та r.

Щоб обчислити C(52,5) — кількість можливих 5-карткових комбінацій у покері — використовуйте мультиплікативну форму замість повних факторіалів, щоб спростити розрахунки. Запишіть у чисельнику добуток п'яти спадних чисел: 52 × 51 × 50 × 49 × 48, а в знаменнику — 5! = 120. Чисельник дорівнює 311,875,200; ділення на 120 дає рівно 2,598,960 можливих роздач.

Для швидкої перевірки на менших числах: C(5,2) = (5 × 4) / (2 × 1) = 10, а C(8,3) = (8 × 7 × 6) / (3 × 2 × 1) = 56.

Khan Academy навчає саме цього прийому зі скороченням, оскільки він дозволяє уникнути обчислення гігантських факторіалів напряму. Цифрова бібліотека математичних функцій NIST (DLMF) наводить аналогічне визначення біноміального коефіцієнта.

Якщо повторення дозволені, формули змінюються, оскільки елементи можна вибирати багаторазово.

• Для перестановок із повтореннями кількість варіантів дорівнює просто n^r: 4-значний PIN-код із цифр 0–9 має 10^4 = 10,000 комбінацій, оскільки кожна з чотирьох позицій незалежно має десять варіантів.
• Для комбінацій із повтореннями формула має вигляд C(n + r − 1, r). Вибір 3 кульок із 5 смаків морозива за можливості повторення дає C(5 + 3 − 1, 3) = C(7,3) = 35.

Порівняйте це з вибіркою без повторень, де кожен вибір зменшує доступну кількість елементів на одиницю. Повторення істотно збільшують підсумкові значення, саме тому на них базується надійність паролів і PIN-кодів — кожен доданий символ багаторазово примножує кількість комбінацій.

Перестановки та комбінації зустрічаються всюди, де потрібно підрахувати варіанти розміщення чи вибору.

• Лотереї використовують комбінації: вибір 6 чисел із 49 дає C(49,6) = 13,983,816 можливих квитків, що визначає ймовірність виграшу джекпоту.
• Карткові ігри також базуються на них: існує 2,598,960 можливих 5-карткових комбінацій у колоді з 52 карт.
• Кібербезпека застосовує перестановки з повтореннями для оцінки кількості можливих паролів або ключів шифрування, що визначає стійкість до зламу методом перебору.
• Статистика та теорія ймовірностей використовують біноміальний коефіцієнт C(n,r) у біноміальному розподілі та трикутнику Паскаля.
• Складання розкладів, жеребкування турнірів, аналіз послідовностей ДНК та вибірковий контроль якості — усе це базується на таких підрахунках.

Encyclopaedia Britannica зазначає, що комбінаторні підрахунки лежать в основі теорії ймовірностей, тому цей калькулятор є незамінним помічником для статистичних та ймовірнісних обчислень.

Кожен елемент у трикутнику Паскаля — це біноміальний коефіцієнт nCr, тому результат обчислення комбінацій фактично відповідає значенню з цього трикутника. Рядок 6 трикутника Паскаля — це 1, 6, 15, 20, 15, 6, 1, що точно відповідає значенням від C(6,0) до C(6,6).

Ці числа є коефіцієнтами у формулі розкладу бінома (a + b)^n, тому C(n,r) називають біноміальним коефіцієнтом.

Звідси випливають дві важливі тотожності:

• правило симетрії C(n,r) = C(n, n−r), тобто C(15,4) = C(15,11) = 1,365
• правило суми: усі коефіцієнти в рядку n у сумі дають 2^n, оскільки C(4,0)+C(4,1)+C(4,2)+C(4,3)+C(4,4) = 1+4+6+4+1 = 16 = 2^4

Wolfram MathWorld та OEIS каталогізують трикутник Паскаля як послідовність A007318.

• Найпоширеніша помилка — вибір неправильної формули: використання перестановки замість комбінації, коли порядок не має значення, завищує результат у r! разів, оскільки nPr враховує кожну невпорядковану групу r! окремих разів. Наприклад, якщо рахувати комітет із 3 осіб із 10 кандидатів як упорядкований, отримаємо P(10,3) = 720 замість правильного C(10,3) = 120.
• Друга помилка — ігнорування повторень: у PIN-коді цифри можуть повторюватися (n^r), а в лотерейних кулях — ні.
• Третя — плутанина між n та r, оскільки у формулах вони не є взаємозамінними.
• Нарешті, уникайте повного розрахунку величезних факторіалів перед діленням; використовуйте метод скорочення дробів, щоб проміжні значення залишалися невеликими, уникаючи переповнення пам'яті чи помилок округлення.

Для будь-яких фіксованих n і r перестановки завжди дорівнюють або перевищують комбінації, оскільки nPr = nCr × r!, де додатковий множник враховує кожен варіант порядку вибраних елементів.

Коли r = 1, вони рівні, оскільки один елемент має лише один варіант розташування: P(20,1) = C(20,1) = 20. У міру збільшення r розрив стрімко зростає. При n = 10 та r = 3 маємо P(10,3) = 720, але C(10,3) = 120 — тобто кількість перестановок рівно в 3! = 6 разів більша. Якщо ж вибрати всі елементи, то P(5,5) = 5! = 120, тоді як C(5,5) = 1.

Саму тому результати з урахуванням порядку зростають набагато швидше, ніж невпорядковані вибірки, і саме тому в лотереях (комбінаціях) шанси на виграш набагато вищі, ніж якби порядок витягування мав значення. Розуміння цього співвідношення допоможе вам перевірити будь-який результат, який видає калькулятор.