Kombinatorika srozumitelně a jednoduše
Při vyslovení slova kombinatorika mnohým lidem, hlavně studentům, vstávají hrůzou vlasy na hlavě. Permutace, variace, kombinace, bez opakování, s opakováním, uspořádané, neuspořádané, na pořadí záleží, na pořadí nezáleží… Kdo se v tom má vyznat? Ve skutečnosti to není tak zlé, což si ukážeme na jednoduchých příkladech.
V kombinatorice řešíme úlohy typu „kolik existuje uspořádání prvků“, „kolika způsoby lze sestavit například trojice z deseti prvků“ apod. Máme tedy celkový počet prvků, který označujeme písmenem n a počet skupin (či tříd), který označujeme písmenem k. Ve většině případů vytváříme tzv. k-tice (dvojice k = 2, trojice k = 3, čtveřice k = 4 atd.) z n prvků.
Vezměme si úplně jednoduchý příklad, kdy máme pouhé dva prvky 1, 2 (jedničku a dvojku). Z nich budeme tvořit dvojice a vysvětlíme si rozdíly mezi variacemi, permutacemi, kombinacemi… ← pod odkazy najdete vzorce a další příklady.
Ponecháme je teď ale stranou (stejně jako matematické definice, které najdete v literatuře) a pomůžeme si pouze tím, že všechny dvojice rozepíšeme. Jelikož máme pouze dva prvky, rozpis nebude dlouhý a rozdíly budou patrné na první pohled.
Variace
Variace, ať už bez opakování, nebo s opakováním, jsou vždy uspořádané neboli vždy záleží na pořadí prvků.
Variace bez opakování:1 2
2 1
Variace s opakováním:1 1
1 2
2 1
2 2
Pokud si prohlédneme dva rozpisy výše, hned vidíme rozdíl mezi variacemi bez opakování a s opakováním. U variací bez opakování je každý prvek zastoupen pouze jedenkrát (nemůže se v řádku našeho rozpisu opakovat), zatímco u variací s opakováním můžeme stejný prvek do výběru zahrnout vícekrát – v 1. řádku se opakuje jednička, ve 4. řádku dvojka. Z toho lze učinit také logický závěr, že variací s opakováním bude více než variací bez opakování.
Příkladem variací s opakováním je třeba heslo – způsoby zjištění, počty možných variací, doba potřebná k prolomení hesla nebo akce „5 mega pro Čechy“ v Eurojackpotu, kde se bez nutnosti extra sázet losuje 7místný kód u vsazeného sloupku s výhrou 1 milion Kč.
Kombinace vs. variace
Níže následuje rozpis kombinací a můžeme vysledovat rozdíl oproti variacím. U variací vždy záleží na pořadí prvků ve výběru, což je stejné, jako když řekneme, že variace jsou uspořádané. Proto 1 2 a 2 1 jsou dvě různé variace (bez opakování) neboli záleží na pořadí jedničky a dvojky (jsou-li v řádku rozpisu na první, nebo na druhé pozici).
Naproti tomu u kombinací na pořadí nezáleží neboli kombinace jsou neuspořádané k-tice (tyto dvě věty mají stejný matematický význam). Proto 1 2 a 2 1 jsou pouze jedna kombinace – nezáleží na tom, zdali je jednička na prvním, nebo na druhém místě (pořadí). Například máte-li ve hře Oko bere či Black Jack dosáhnout oka (součtu jednadvacet), je lhostejné, zdali dostanete jako první kartu eso a jako druhou desítku, nebo obráceně.
| nebo |
Podobně například u číselných loterií nezáleží na tom, v jakém pořadí jsou vítězná čísla tažena. Víte, v které loterii je největší počet všech možných kombinací?
Kombinace bez opakování1 2 (nebo 2 1)
Kombinace s opakováním1 1 (nebo
1 22 1)2 2
U kombinací s opakováním stále platí, že nezáleží na pořadí prvků (= jsou neuspořádané), ale jednotlivé prvky se mohou ve výběru (v řádku) opakovat. Opět také platí, že kombinací s opakováním je více než kombinací bez opakování, ale méně než variací s opakováním, protože na rozdíl od nich je 1 2 a 2 1 jakožto jedna kombinace ve druhém řádku.
Permutace
Permutace jsou pouze zvláštním případem variací, kdy počet prvků ve výběru je roven celkovému počtu prvků (n = k). To znamená, máme-li dva prvky, tvoříme (rozepisujeme) dvojice, máme-li tři prvky, tvoříme trojice atd. Rozpis permutací by byl stejný jako u variací, protože máme dva prvky a rozepisuje (vybíráme) dva prvky (matematicky n = 2 = k).
Kombinatorická pravidla
V kombinatorice se uplatňují dvě kombinatorická pravidla, a sice kombinatorické pravidlo součtu a kombinatorické pravidlo součinu. Opět se dají vysvětlit jednoduše i bez matematických definic.
Kombinatorické pravidlo součtu
Například máme dvě skupiny (množiny), z nich první má prvky 1, 3 a druhá 5, 6. Kolika způsoby lze vybrat právě jeden prvek z těchto dvou skupin?
Jelikož obě skupiny nemají ani jeden společný prvek (jazykem matematiky: jsou po dvou disjunktní), můžeme počty prvků v obou skupinách (množinách) sečíst: 2 + 2 = 4. Jeden prvek z obou množin lze vybrat čtyřmi způsoby.
Jestliže by však skupiny měly nějaké prvky společné, je nutné je z celkového součtu vyloučit. Řečeno jazykem matematiky: jde o sjednocení dvou množin a odečet jejich průniku. Příklad: máme dvě skupiny, první má dva prvky 3, 5 a druhá čtyři prvky 1, 5, 6, 7. Skupiny však mají jedno číslo společné (pětku), proto kombinatorické pravidlo součtu uplatníme následovně: 2 + 4 – 1 = 5. Právě jeden prvek z obou skupin lze vybrat pěti způsoby.
Kombinatorické pravidlo součinu
Na kombinatorickém pravidlu součinu také není nic složitého, což lze nejlépe ukázat na příkladech.
Příklad 1: Kolika způsoby lze v pokeru získat nejvyšší možnou kombinaci, tedy královský fleš?
Řešení: královský fleš je postupka v barvě od desítky do esa. Existuje tedy pouze jeden způsob, jak tuto postupku docílit, ale postupka může mít čtyři různé barvy (piky, kříže, srdce, káry). Užijeme-li kombinatorické pravidlo součinu, královský fleš je možné získat 1 × 4 = 4 způsoby.
Příklad 2: Třikrát po sobě hodíte klasickou hrací kostkou (která má jedno až šest ok či teček). Kolik různých možností (uspořádaných trojic) může vzniknout?
| … |
Řešení: při třech hodech jednou kostkou může vždy padnout číslo 1 až 6. Počet možností – různých (uspořádaných) trojic – které mohou vzniknout je tedy 6 × 6 × 6 = 216.