Комбінаторика без повторення

Під комбінаторикою без повторення розуміються різні набори, які можуть бути сформовані з елементами «n», вибраними з x в x. Кожен набір повинен відрізнятися від попереднього хоча б одним із своїх елементів (порядок не має значення), і їх не можна повторити.

Комбінаторика без повторення широко використовується в статистиці та математиці. Це відповідає багатьом реальним життєвим ситуаціям, і його застосування досить просто.

Візьмемо, наприклад, студента, який має іспит із 4 питань. Із чотирьох запитань він повинен вибрати три. Скільки різних комбінацій міг скласти учень? Якщо ми трохи роздумуємо, ми побачимо (фактично не застосовуючи формулу), що студент може вибрати, як відповісти на 3 запитання чотирма різними способами.

• Набір / варіант 1: Дайте відповіді на запитання 1,2,3.
• Набір / варіант 2: Дайте відповіді на запитання 1,2,4.
• Набір / варіант 3: Дайте відповіді на запитання 1,3,4.
• Набір / варіант 4: Дайте відповіді на запитання 2,3,4.

Як бачимо, учень може сформувати 4 набори (n) з 3 елементів (x). Отже, комбінаторика без повторення говорить нам, як сформувати або згрупувати кінцеву кількість даних / спостережень, у групи певної величини без можливості повторення будь-якого з елементів у кожній групі. Це основна різниця між комбінаторним з повторенням (елементи в кожній групі можна повторити) та комбінаторним без повторення (жоден елемент не може бути повторений у кожній групі)

Щоб підкреслити в цьому прикладі, що мова йде про комбінаторику без повторення, оскільки студент не може вибрати одне із запитань більше одного разу. Тому елементи множин не можна повторювати.

У попередньому випадку, враховуючи, що загальна кількість елементів невелика, а кількість набору велика, кількість варіантів невелика і може бути легко виведена без застосування формули. У разі безпосереднього застосування формули чисельник мав би значення 24 (4 * 3 * 2 * 1), а знаменник - 6 (3 * 2 * 1 * 1), за допомогою якого ми могли б отримати розрахунки таким же чином не замислюючись про те, як ми могли б згрупувати ці чотири запитання у три набори.

Як розрахувати комбінаторику без повторення?

Формула комбінатора без повторення:

Де:

• п = Всього спостережень
• х = Кількість вибраних елементів

Приклад комбінаторний без повторення

Уявімо собі військовий взвод із 12 солдатів. Капітан армії хоче сформувати групи з 2 солдатів, щоб просочитися за ворожі рубежі в різних точках, скільки різних груп він міг сформувати?

Для вирішення проблеми спочатку ми повинні визначити загальну кількість елементів. У цьому випадку загалом є 12 солдатів, тому ми вже маємо своїх росіян. Оскільки капітан хоче групи з 2 осіб, ми вже знаємо, що таке х. Знаючи це, ми можемо замінити у формулі і мати кількість комбінацій груп 2.

• п = 12
• х = 2

При заміні:

Застосовуючи факторіал для знаменника, ми мали б 12 * 11 * 10 * … * 1 = 479,001,600. Для знаменника маємо 2 * 1 * 10 * 9 * 8… * 1 = 7 257 600. Наше комбінаторне число = 479 001 600/7 257 600 = 66.

Як ми бачимо, капітан може сформувати 66 різних пар солдатів з числа 12, які у нього є.