Hazardní hry › Pravděpodobnost › Permutace

Permutace

Permutací označujeme jedno z možných uspořádání prvků množiny, přičemž výsledné uspořádání má stejný počet prvků jako množina. Má-li množina n prvků, permutace je jednou z možných n-tic. Výpočty nejsou náročné a budou jasné z příkladů.

Pokud se prvky v množině neopakují (například čísla 1 2 3 nebo písmena A B C D), hovoříme o permutacích bez opakování. Jestliže se některé prvky v množině mohou opakovat (například 1 1 2 5 nebo A A B C C), mluvíme o permutacích s opakováním.

Má-li množina například čtyři prvky A B C D nebo A B B C, tak pomocí permutací určíme, kolik čtveřic z nich můžeme vytvořit – tvoříme tedy pouze a jen čtveřice, neboť počet prvků ve výsledném uspořádání musí být shodný s počtem prvků množiny. Tím se permutace liší od variací a kombinací.

U variací a kombinací bychom se například mohli ptát, kolik různých dvojic (u variací uspořádaných, u kombinací neuspořádaných) lze vytvořit ze čtyř prvků. Permutace jsou zvláštní formou variací, kdy celkový počet prvků (n) je roven počtu prvků ve výběru (k). Srovnání variací, permutací a kombinací a jednoduché ilustrativní příklady najdete na stránce kombinatorika jednoduše.

Permutace bez opakování

Začněme tím jednodušším. Jestliže se prvky ve výběru nemohou opakovat, pak počet všech možných uspořádání je dán vztahem:

Čili „en faktoriál“, přičemž faktoriálem označuje součin všech celých kladných čísel menších nebo rovných n (speciálním případem je 0!, který je roven jedné).

Příklad 1

Mějme tři různé prvky 1 2 3. Kolika způsoby je možné je rozepsat (uspořádat), jinými slovy, kolik existuje permutací?

Řešení: P(3) = 3! = 3 × 2 × 1 = 6.

Pro kontrolu můžeme permutace rozepsat:
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

S rostoucím počtem prvků se však počet permutací rapidně zvyšuje a na rozpis by bylo třeba využít výpočetní techniky. Například:

4! = 24
5! = 120
6! = 720
7! = 5 040
8! = 40 320 atd.

Příklad 2: Počet způsobů uspořádání karet v pokeru

Poker se hraje s balíčkem, který obsahuje 52 karet. Kolika způsoby je možné všechny karty uspořádat (poskládat v řadě za sebou)?

…

Řešení: že jde o permutace bez opakování, již napovídá úkol všechny karty uspořádat či seřadit. Bez opakování proto, že v balíčku je každá karta zastoupená pouze jedenkrát (i když jsou v balíčku například 4 esa, tak každé eso má svou barvu, tím je unikátní). Na obrázku je zachyceno jedno ze základních uspořádání od dvojky po eso v každé barvě. Pořadí všech karet je možné různě měnit. Při 52 kartách docílíme obrovského počtu možností (permutací).

P(52) = 52! = 52 × 51 × 50 × 49 × … × 2 × 1 = = 80 658 175 170 943 900 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000.

Tedy asi osmička a 67 nul za ní… Jak si představit takto obrovská čísla? Můžete si prohlédnout prezentaci Fantastický výlet do makro- a mikrokosmu.

Permutace s opakováním

Mohou-li se prvky ve výběru opakovat, pak počet permutací (s opakováním) určíme podle vzorce:

Písmenem k označujeme počet skupin (tříd), písmenem n s indexem počet prvků v dané skupině. Úplně nejjednodušší je asi tento příklad.

Příklad 3

Mějme následující tři prvky 1 1 2 (jednička se opakuje dvakrát). Kolik permutací s opakováním můžeme vytvořit?

Řešení: celkový počet prvků je tři, tedy n = 3, počet skupin k = 2, přičemž první skupinu tvoří dvě jedničky čili n₁ = 2 a druhou skupinu tvoří jedna dvojka, tedy n₂ = 1. Dosadíme do vzorce:

P_2,1(3) = 3! ÷ (2! × 1!) = 3.

Rozpis možností vypadá následovně:1 1 2 1 2 1 2 1 1

Opět platí, že počet možností se s rostoucím počtem prvků rychle zvyšuje a provádět rozpis ručně by bylo téměř nemožné.

Příklad 4: Uspořádání písmen ve slově MISSISSIPPI

Kolika způsoby je možné poskládat za sebou písmena ze slova MISSISSIPPI? Poznámka: slova samozřejmě nemusejí dávat smysl, jde pouze o možná seřazení písmem.

Řešení: ve slově MISSISSIPPI je celkem 11 písmen, z toho M 1krát, I 4krát, S 4krát a P 2krát. Seřazujeme všechna písmena a některá z nich se opakují → permutace s opakováním.

P_1,4,4,2(11) = 11! ÷ (1! × 4! × 4! × 2!) = 39 916 800 ÷ 1 152 = 34 650 různých seřazení písmen.

Příklad 5: Permutace při hodu šesti hracími kostkami

Permutace s opakováním jsme s výhodou použili u číselné loterie Kostky od společnosti Sazka. Hra simuluje hod šesti klasickými kostkami (každá kostka má jeden až šest puntíků) a lze v ní mj. sázet na součty. Můžeme snadno určit, že součet čísel na šesti kostkách může dosahovat hodnoty od 6 (padnou samé jedničky) do 36 (padnou samé šestky).

Poměrně jednoduché je zjistit počet všech možností, například pomocí kombinatorického pravidla součinu: máme šest kostek a na každé může padnout šest čísel, tj.:

6 × 6 × 6 × 6 × 6 × 6 = 6⁶ = 46 656.

Případně můžeme využít variací s opakováním. Opět, máme 6 kostek (n = 6) a každé číslo na kostce se může opakovat nanejvýš 6krát (k = 6). Počet variací s opakováním zjistíme jako n^k čili 6⁶ = 46 656.

Abychom zjistili pravděpodobnost, že se nám podaří uhodnout určitý součet šesti kostek (z intervalu 6 až 36), musíme znát také počet možností (na základě permutací s opakováním), jakými lze ten který součet sestavit. Například u součtu 6 je situace velmi jednoduchá, neboť existuje pouze jedna možnost.

Podobně jednoduché je určit počet permutací pro součet 7 či 35. Těch je šest, například u sedmičky: 1+1+1+1+1+2, 1+1+1+1+2+1, 1+1+1+2+1+1, 1+1+2+1+1+1, 1+2+1+1+1+1, 2+1+1+1+1+1. Vidíme, že pouze dvojka mění pozici, jiné možnosti nejsou. Ale co takhle například součet 11?

Trochu složitější případ – součet 11

Předem můžeme prozradit, že počet možností, jak sestavit součet 11 je 252, a to už by se vám asi vypisovat nechtělo (u součtu 21 je to přes 4 000 možností…).

Pro zjištění počtu možností, jakými lze docílit součtu 11 při hodu šesti kostkami využijeme permutací s opakováním. K tomu si vytvoříme pomocnou tabulku, do které zapíšeme všechny „základní“ způsoby, kterými lze součtu 11 dosáhnout. „Základní“ proto, že nám například stačí vědět, že k součtu 11 potřebujeme 5 jedniček a jednu 6. A na které kostce se objeví šestka je nám jedno, neboť právě pomocí permutací s opakováním zjistíme, kolika těmito dílčími způsoby lze součtu 11 dosáhnout. Vezměme si ale trošku složitější dílčí součet 11:

Součet kostek dává 11, přičemž v tomto případě tři jedničky, dvě dvojky a jednu čtyřku můžeme nakombinovat 60 různými způsoby (permutacemi s opakováním). Všechny pomocné výpočty jsou uvedeny v následující tabulce.

Výpočet permutací u součtu 11 při hodu 6 kostkami

Ve všech případech je počet prvků n = 6 (hází se šesti kostkami). U sestavy 1+1+1+2+2+4 pak máme tři skupiny k = 3; tři jedničky n₁ = 3, dvě dvojky n₂ = 2 a jednu čtyřku n₃ = 1. Dosadíme do známého vzorce a získáme:

P_3,2,1(6) = 6! ÷ (3! × 2! × 1!) = 720 ÷ 12 = 60.

Součet 11 u dílčí sestavy 1+1+1+2+2+4 lze docílit 60 způsoby (permutací). Takto pokračujeme i pro ostatní sestavy, nakonec vše sečteme a získáme počet vyhrávajících možností 252. Pravděpodobnost, že padne součet 11, pak získáme tak, že podělíme počet vyhrávajících možností počtem celkových možností, tedy 252 ÷ 46 656 = 0,0054012 neboli 1 ku 185.

Je jasné, že takto postupovat pro všechny součty by bylo trochu zdlouhavé. Při hodnocení loterie Kostky od Sazky bylo využito makra, které vygenerovalo všech 46 656 možných rozložení kostek a pak již bylo snadné provést součty a výpočty pravděpodobností. Nicméně příklad dobře ilustruje využití permutací s opakováním a postup jejich výpočtu.

Související témata a zajímavosti:

→ Kombinatorika
→ Variace
→ Kombinace
→ Kostkový problém ze 17. století
→ Články o pravděpodobnosti