Kalkulačka permutací a kombinací

Permutace použijte tehdy, když záleží na pořadí nebo uspořádání vybraných prvků:

• určování pořadí (1., 2., 3. místo)
• rovnání knih na polici
• vytváření hesel nebo PIN kódů
• rozsazení hostů
• telefonní čísla

Kombinace použijte tehdy, když pouze vybíráte podmnožinu a na pořadí nezáleží:

• výběr členů týmu
• volba loterijních čísel
• výběr jídel z menu
• sestavování výborů

Užitečný test: pokud záměna dvou vybraných prvků změní výsledek, použijte permutace; pokud na záměně nezáleží, použijte kombinace.

Loterijní čísla to dokonale ilustrují — v loterii Mega Millions se vybírá 5 čísel ze 70 a 1 číslo z 25: C(70,5) × 25 = 302 575 350 možných tiketu. Pokud by záleželo na pořadí, existovalo by P(70,5) × 25 = 36 309 042 000 možností — 120krát více.

Základní permutace: P(n,r) = n!/(n-r)!. P(10,3) = 10!/7! = 10×9×8 = 720.

Základní kombinace: C(n,r) = n!/[r!(n-r)!]. C(10,3) = 10!/(3!×7!) = 720/6 = 120.

S povoleným opakováním: permutace = n^r (např. 4místný PIN z číslic 0–9 má 10⁴ = 10 000 možností).

Kombinace s opakováním: C(n+r-1, r) — výběr 3 kopečků z 5 druhů zmrzliny s možností opakování dává C(7,3) = 35.

Pro velké hodnoty použijte multiplikativní vzorec, abyste se vyhnuli výpočtu obrovských faktoriálů: C(52,5) = (52×51×50×49×48)/(5×4×3×2×1) = 2 598 960 — počet možných pětikaretních pokerových kombinací.

Bezpečnost hesel: 8místné heslo využívající velká a malá písmena, číslice a 10 symbolů (celkem 72 znaků) má 72⁸ = 722 trilionů permutací s opakováním — což při rychlosti 1 miliardy pokusů za sekundu vyžaduje pro útok hrubou silou přibližně 22 800 let. Přidání pouhých 2 znaků (10místné heslo) zvyšuje tento počet na 3,7 kvadrilionu — což je 5 140krát těžší prolomit.

• V genetice je počet způsobů výběru 23 párů chromozomů z 46 chromozomů rodiče C(46,23) ≈ 8,2 miliardy, což vysvětluje genetickou rozmanitost.
• V kontrole kvality zahrnuje výběr 5 položek ze šarže 100 kusů pro testování C(100,5) = 75 287 520 možných vzorků.
• V turnajových pavoucích je počet možných tipů na NCAA March Madness 2⁶³ ≈ 9,2 kvintilionu — což je důvod, proč nikdo nikdy nepředpověděl dokonale přesný pavouk.

Permutace je uspořádané seskupení prvků, zatímco kombinace je neuspořádaný výběr — jediný rozdíl spočívá právě v pořadí.

Pokud vyberete písmena A, B a C, jsou uspořádání ABC a CAB dvě různé permutace, ale stejná kombinace, protože u kombinace záleží pouze na tom, které prvky byly vybrány, nikoli na jejich pořadí. Jak vysvětluje Encyclopaedia Britannica, kombinatorika je obor matematiky věnovaný počítání takových uspořádání a výběrů.

Rychlý test: zeptejte se, zda záměna dvou vybraných prvků změní výsledek. Určení držitelů zlaté, stříbrné a bronzové medaile se změní, pokud prohodíte dva běžce, takže na pořadí záleží a použijete permutace. Výběr tří přísad na pizzu se při prohození nezmění, takže použijete kombinace.

Vzorec pro permutace je nPr = n! / (n − r)! a vzorec pro kombinace je nCr = n! / [r! × (n − r)!], kde n! (n faktoriál) je součin všech celých čísel od 1 do n.

Pro výpočet P(10,3) spočítejte 10! / 7!, což se zjednoduší na 10 × 9 × 8 = 720. Pro výpočet C(10,3) vydělte tento výsledek hodnotou 3! = 6, čímž získáte 120. Samotný faktoriál roste velmi rychle: 5! = 120 a 10! = 3 628 800.

Wolfram MathWorld definuje kombinační číslo C(n,r) přesně tímto způsobem. Protože nCr vydělí r! pořadí, která permutace počítají zvlášť, je nCr pro stejná n a r vždy menší nebo rovno nPr.

Chcete-li vypočítat C(52,5) — počet pětikaretních pokerových kombinací — začněte spíše multiplikativní formou než plnými faktoriály, aby čísla zůstala zvládnutelná. Čitatele zapište jako pět nejvyšších klesajících činitelů, 52 × 51 × 50 × 49 × 48, a jmenovatele jako 5! = 120. Čitatel je roven 311 875 200; dělením 120 získáte přesně 2 598 960 možných kombinací.

Pro menší kontrolu: C(5,2) = (5 × 4) / (2 × 1) = 10 a C(8,3) = (8 × 7 × 6) / (3 × 2 × 1) = 56.

Khan Academy vyučuje tuto zkrácenou metodu krácení, protože se vyhne přímému výpočtu obrovských faktoriálů. NIST Digital Library of Mathematical Functions (DLMF) uvádí stejnou definici kombinačního čísla, jaká je použita zde.

Když je povoleno opakování, vzorce se mění, protože prvky lze použít vícekrát.

• Pro permutace s opakováním je počet jednoduše n^r: 4místný PIN sestavený z číslic 0–9 má 10^4 = 10 000 možností, protože každá ze čtyř pozic má nezávisle na sobě deset možností.
• Pro kombinace s opakováním je počet C(n + r − 1, r). Výběr 3 kopečků ze 5 druhů zmrzliny s opakováním dává C(5 + 3 − 1, 3) = C(7,3) = 35.

Srovnejte to s výběrem bez opakování, kde každý výběr zmenší nabídku o jeden prvek. Opakování dramaticky zvyšuje celkové počty, což je důvod, proč na něm závisí síla hesel a bezpečnost PIN kódů — každý přidaný znak násobí počet možností.

Permutace a kombinace se objevují všude tam, kde počítáte uspořádání nebo výběry.

• Loterie využívají kombinace: výběr 6 čísel ze 49 dává C(49,6) = 13 983 816 možných tiketu, což určuje pravděpodobnost výhry jackpotu.
• Kartářní hry na ně spoléhají také — v balíčku 52 karet existuje 2 598 960 možných pětikaretních pokerových kombinací.
• Kybernetická bezpečnost využívá permutace s opakováním k měření počtu možných hesel nebo klíčů, což přímo ovlivňuje odolnost vůči útokům hrubou silou.
• Statistika a pravděpodobnost využívají kombinační číslo C(n,r) v binomickém rozdělení a Pascalově trojúhelníku.
• Plánování harmonogramů, nasazování do turnajů, analýza sekvencí DNA i odběr vzorků při kontrole kvality — to vše závisí na těchto výpočtech.

Encyclopaedia Britannica uvádí, že kombinatorické počítání tvoří základ teorie pravděpodobnosti, a proto se tato kalkulačka přirozeně doplňuje s nástroji pro pravděpodobnost a statistiku.

Každá položka v Pascalově trojúhelníku je kombinační číslo nCr, takže výstup kombinací z kalkulačky je doslova odečítáním hodnoty z tohoto trojúhelníku. Řádek 6 Pascalova trojúhelníku je 1, 6, 15, 20, 15, 6, 1 — přesně C(6,0) až C(6,6).

Tato čísla jsou koeficienty v binomickém rozvoji (a + b)^n, což je důvod, proč se C(n,r) nazývá kombinační číslo.

Z toho přímo vyplývají dvě identity:

• pravidlo symetrie C(n,r) = C(n, n−r), takže C(15,4) = C(15,11) = 1 365
• pravidlo součtu, že všechny koeficienty v řádku n dají v součtu 2^n, protože 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 a OEIS katalogizují Pascalův trojúhelník jako posloupnost A007318.

• Nejčastější chybou je výběr špatného nástroje: použití permutace v případě, kdy na pořadí nezáleží, zvětší výsledek r!-krát, protože nPr započítá každou neuspořádanou skupinu r!-krát samostatně. Například zacházení s tříčlenným výborem ze 10 lidí jako s uspořádaným dává P(10,3) = 720 místo správného C(10,3) = 120.
• Druhou chybou je opomenutí, zda je povoleno opakování — PIN číslice opakuje (n^r), ale loterie nikoli.
• Třetí chybou je záměna n a r, protože vzorce vůči nim nejsou symetrické.
• Nakonec se vyvarujte výpočtu obrovských faktoriálů v plné výši s následným dělením; použijte metodu krácení, aby mezihodnoty zůstaly malé a vy jste se vyhnuli přetečení nebo chybám ze zaokrouhlování.

Pro libovolné pevné n a r permutace vždy dosahují kombinací nebo je převyšují, protože nPr = nCr × r!, přičemž tento dodatečný faktor zohledňuje každé možné uspořádání vybraných položek.

Když r = 1, jsou si rovny, protože jediná položka má pouze jedno uspořádání: P(20,1) = C(20,1) = 20. S rostoucím r se rozdíl rychle zvětšuje. Při n = 10 a r = 3 je P(10,3) = 720, ale C(10,3) = 120 – počet permutací je přesně 3! = 6krát větší. Pokud vybereme všechny položky, P(5,5) = 5! = 120, zatímco C(5,5) = 1.

Právě proto narůstá počet uspořádaných výsledků mnohem rychleji než neuspořádaný výběr a proto mají loterie (kombinace) mnohem lepší šance, než kdyby záleželo na pořadí tažení. Porozumění tomuto poměru vám pomůže zkontrolovat správnost jakéhokoli výsledku, který tato kalkulačka věku vrátí.