Na jednom společném příkladě odvodíme základní kombinatorické principy – variace, permutace a kombinace.
Čtyři kamarádi se zastavili u stánku se zmrzlinou, ve kterém nabízejí zmrzlinu šesti příchutí: kakaovou, vanilkovou, oříškovou, pistáciovou, jahodovou a citrónovou. Zamyslíme se nad různými kombinatorickými otázkami souvisejícími s touto situací:
Kolika různými způsoby se můžou kamarádi u stánku postavit do řady?
Kolika různými způsoby si můžou každý vybrat jeden kopeček zmrzliny?
Kolika různými způsoby si můžou každý vybrat jeden kopeček zmrzliny tak, aby se žádná příchuť neopakovala?
Kolik můžeme vytvořit různých zmrzlinových pohárů se čtyřmi kopečky zmrzliny různých příchutí?
Kolik můžeme vytvořit různých zmrzlinových pohárů se čtyřmi kopečky zmrzliny, přičemž se příchutě můžou vyskytovat i vícekrát?
Nyní předpokládejme, že je kamarádů devět a každý z nich si objedná jeden kopeček zmrzliny. Kolika různými způsoby může vypadat jejich objednávka, když víme, že tři z nich si objednali kakaovou, tři vanilkovou, dva pistáciovou a jeden jahodovou?
Jde o proces, který probíhá postupně ve čtyřech nezávislých krocích. V prvním kroku vybereme libovolně ze všech čtyř lidí, kdo se postaví první. Pro každou z těchto čtyř možností potom ve druhém kroku vybereme libovolně ze zbývajících tří lidí, kdo bude druhý. Pro obsazení prvních dvou pozic tedy máme $4\cdot 3=12$ možností. No a pro každou z těchto $12$ možností máme ve třetím kroku dvě možnosti, kdo bude třetí, přičemž na čtvrtou pozici už zůstane pouze jedna osoba. Dostáváme tedy, že počet všech možných seřazení je
$\square$
Proces má čtyři nezávislé fáze, ve kterých postupně každý z kamarádů vybírá ze všech šesti dostupných příchutí nezávisle na volbě ostatních. První kamarád má tak na výběr ze šesti možností a pro libovolný jeho výběr má i druhý kamarád šest možností a pro libovolný jejich společný výběr má i třetí kamarád šest možností atd. Jejich možnosti se tedy navzájem násobí a počet všech různých výběrů je
$\square$
Tak jako v případě b. je opět možné výběr rozdělit do čtyř nezávislých fází. Tentokrát se ovšem možnosti postupně zužují. První kamarád vybírá ze všech šesti příchutí, druhý už jenom ze zbývajících pěti, třetí ze čtyř, a poslední ze tří. Dostáváme tedy, že počet všech různých výběrů za těchto podmínek je
$\square$
Otázku můžeme ekvivalentně přeformulovat následovně: Kolika různými způsoby si můžou kamarádi vybrat každý jeden kopeček zmrzliny tak, aby se žádná příchuť neopakovala, přičemž nás nezajímá, kdo si kterou příchuť vybral? Můžeme tedy použít řešení c., ale tentokrát při výběru nezáleží na pořadí, tj. všechna přeuspořádání jednoho výběru jsou považována za stejná. V případě c. se každý výběr objevuje ve $4! = 24$ uspořádáních (podle bodu a.), takže musíme výsledek c. vydělit $4!$ a dostaneme
možností.
$\square$
Budeme tedy vybírat čtyři příchutě ze šesti bez jakéhokoli pořadí a bez omezení na opakování. Ukážeme si, že tuto úlohu můžeme převést na úlohu typu d. správnou interpretací.
Výběry lze „kódovat“ jako řetězce obsahující pět symbolů $|$ a čtyři symboly $\bullet$ následovně: Symboly $|$ budou oddělovače vytvářející přihrádky pro jednotlivé příchutě41 a symboly $\bullet$ budou reprezentovat kopečky zmrzliny.
Například, výběru dvou kopečků kakaové, jednoho kopečku pistáciové a jednoho kopečku jahodové bude odpovídat řetězec
Naopak, libovolný řetězec sestavený z pěti symbolů $|$ a čtyř symbolů $\bullet$ reprezentuje nějaký výběr. Například řetězec
odpovídá výběru tří kopečků vanilkové a jednoho kopečku citrónové.
Takovýmto způsobem můžeme jednoznačně znázornit všechny možné výběry. Počet možných výběrů tedy bude odpovídat počtu všech možných řetězců $|$ a $\bullet$, ve kterých se vyskytuje právě pět symbolů $|$ a čtyři symboly $\bullet$.
Kolik tedy existuje řetězců $|$ a $\bullet$ (binárních řetězců), ve kterých se vyskytuje právě pět symbolů $|$ a čtyři symboly $\bullet$? V řetězci o celkové délce $9$ znaků stačí vybrat $4$ pozice pro $\bullet$ (což je stejné jako vybrat $5$ pozic pro $|$). Na každé pozici může být pouze jeden symbol, tedy se ve výběru nemůžou opakovat, a nezáleží na tom, v jakém pořadí pozice vybereme. Dostali jsme se tedy do stejné úlohy jako v bodě d., ale nyní vybíráme čtyři (pozice) z devíti možností:
$\square$
Na tuto úlohu budeme taky moci aplikovat model z případu d. Tentokrát nebudeme pro osoby vybírat zmrzlinu, ale pro zmrzlinu vybírat její konzumenty. Je to proces, který proběhne ve čtyřech nezávislých krocích. Nejdřív z devíti kamarádů vybereme tři, kteří dostanou kakaovou zmrzlinu. To odpovídá výběrům $3$ prvků z $9$, ve kterých se vybrané prvky neopakují (každý má pouze jeden kopeček zmrzliny) a nezáleží na pořadí jejich výběru. Podle bodu d. tedy pro tento krok máme $\frac{9!}{6!\cdot 3!}$ možností. V dalším kroku ze zbylých šesti kamarádů vybereme další tři, kteří dostanou vanilkovou zmrzlinu. Pro to máme $\frac{6!}{3!\cdot 3!}$ možností. Dále ze tří vybereme dva kamarády, kteří dostanou pistáciovou zmrzlinu – analogicky, máme $\frac{3!}{1!\cdot 2!}$ možností. No a na závěr zůstane jedna osoba, která bude mít jahodovou zmrzlinu – pouze 1 možnost. Libovolnou možnost z jednoho kroku může následovat libovolná možnost z dalšího kroku, proto počty možností v jednotlivých krocích spolu vynásobíme, čímž dostaneme konečný výsledek
$\square$