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 n1 = 2 a druhou skupinu tvoří jedna dvojka, tedy n2 = 1. Dosadíme do vzorce:
P2,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.
P1,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 = 66 = 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 nk čili 66 = 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.
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 n1 = 3, dvě dvojky n2 = 2 a jednu čtyřku n3 = 1. Dosadíme do známého vzorce a získáme:
P3,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.