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

Комбинаториката без повторение се разбира като различните набори, които могат да бъдат оформени с «n» елементи, избрани от x в x. Всеки набор трябва да се различава от предишния поне по един от неговите елементи (редът няма значение) и те не могат да бъдат повторени.

Комбинаториката без повторение е често използвана в статистиката и математиката. Това се вписва в много ситуации от реалния живот и приложението му е съвсем просто.

Вземете например студент, който има изпит с 4 въпроса. От 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 войници, следователно вече имаме своя n. Тъй като капитанът иска групи от по 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-те, които има.