Kombinatorika bez opakování

Kombinatoriku bez opakování chápeme jako různé množiny, které lze vytvořit pomocí prvků «n» vybraných z x v x. Každá sada se musí od té předchozí lišit alespoň v jednom ze svých prvků (na pořadí nezáleží) a nelze je opakovat.

Kombinatorika bez opakování se běžně používá ve statistice a matematice. To se hodí pro mnoho situací v reálném životě a jeho aplikace je docela přímočará.

Vezměme si například studenta, který má zkoušku se 4 otázkami. Ze 4 otázek musí vybrat tři: Kolik různých kombinací může student vytvořit? Pokud bychom trochu uvažovali, viděli bychom (aniž bychom skutečně použili vzorec), že si student může vybrat, jak odpovědět na 3 otázky čtyřmi různými způsoby.

• Sada / možnost 1: Odpovědi na otázky 1,2,3.
• Sada / možnost 2: Odpovědi na otázky 1,2,4.
• Sada / možnost 3: Odpovědi na otázky 1,3,4.
• Sada / možnost 4: Odpovědi na otázky 2,3,4.

Jak vidíme, student může vytvořit 4 sady (n) ze 3 prvků (x). Kombinatorika bez opakování nám proto říká, jak vytvořit nebo seskupit konečné množství dat / pozorování ve skupinách s určitým množstvím, aniž by bylo možné v každé skupině opakovat jakýkoli z prvků. To je hlavní rozdíl mezi kombinačním s opakováním (prvky v každé skupině lze opakovat) a kombinačním bez opakování (v každé skupině nelze opakovat žádný prvek)

V tomto příkladu zdůrazním, že jde o kombinatoriku bez opakování, protože student se nemůže rozhodnout položit některou z otázek vícekrát. Proto nelze prvky sad opakovat.

V předchozím případě, vzhledem k tomu, že celkový počet prvků je malý a množství sady je vysoké, je počet možností malý a lze jej snadno odvodit bez použití vzorce. V případě přímého použití vzorce by čitatel byl 24 (4 * 3 * 2 * 1) a jmenovatel by byl 6 (3 * 2 * 1 * 1), s nimiž bychom dospěli k výpočtu stejným způsobem aniž bychom přemýšleli o tom, jak bychom tyto čtyři otázky mohli seskupit do tří.

Jak vypočítat kombinatoriku bez opakování?

Vzorec kombinačního bez opakování je:

Kde:

• n = Celkový počet pozorování
• X = Počet vybraných položek

Příklad kombinační bez opakování

Představme si vojenskou četu 12 vojáků. Kapitán armády chce vytvořit skupiny 2 vojáků, aby se infiltrovali za nepřátelské linie na různých místech, kolik různých skupin by mohl vytvořit?

Abychom problém vyřešili, musíme nejprve identifikovat celkový počet prvků. V tomto případě je celkem 12 vojáků, proto už máme naše n. Protože kapitán chce skupiny po 2, už víme, jaké je naše x. S tímto vědomím bychom mohli ve vzorci nahradit a mít počet skupinových kombinací 2.

• n = 12
• X = 2

Při nahrazování:

Při použití faktoriálu pro jmenovatele bychom měli 12 * 11 * 10 * … * 1 = 479,001,600. Pro jmenovatele máme 2 * 1 * 10 * 9 * 8… * 1 = 7 257 600. Naše kombinatorické číslo je = 479 001 600/7 257 600 = 66.

Jak vidíme, kapitán může tvořit 66 různých dvojic vojáků z 12, které má.