Kombinatorika
Kapitoly: Kombinatorika, Variace, Permutace, Kombinace, Variace s opakováním, Kombinace s opakováním, Kolik existuje různých PINů, Kalkulačka: Kombinační číslo
Potřebujete vědět, kolik různých pětic karet můžete vybrat z balíčku 32 karet? To je přesně typ úlohy, kterou řeší kombinatorika. Existují dvě základní kombinatorická pravidla — součtu a součinu. Všechny ostatní postupy jsou jen rozšířením těchto základních principů.
Kombinatorické pravidlo součtu
Pravidlo součtu je velice jednoduché — říká nám, že pokud máme množiny A, B, které nemají žádný společný prvek, pak počet všech možných způsobů výběru jednoho prvku ze sjednocení A ∪ B je roven |A| + |B|, tj. součtu velikostí množin.
Začneme nějakým lehkým příkladem. Máme 6 červených míčků a 8 modrých míčků. Tyto míčky vysypeme do jednoho osudí. Kolik máme celkem možností, když budeme losovat jeden míček? Na začátku jsme měli množinu červených míčků, označme jako množinu A, pak množinu modrých míčků, označme B. Tyto množiny jsou disjunktní, tzn., že nemají žádný stejný míček. Chceme vylosovat jeden míček, takže máme celkem |A| + |B| = 6 + 8 = 14 možností. To je celé.
Kombinatorické pravidlo součinu
Máme opět dvě množiny, Z a M. Množina Z obsahuje tři ženy a množina M čtyři muže. Nyní se ptáme, kolik různých párů muž—žena můžeme z těchto množin vytvořit? O co se snažíme — vždy vezmeme jednu ženu a jí přiřadíme nějakého muže. Počet všech párů spočítáme takto: vezmeme jednu ženu, Katku, a postupně k ní přiřadíme všechny muže. Dostaneme tak 4 různé páry, protože k ní můžeme přiřadit celkem 4 různé pány. Totéž uděláme pro zbývající dvě ženy, ty také vytvoří vždy další 4 páry. A to je vše, máme celkem 4 + 4 + 4 = 12 párů.
Co jsme ve skutečnosti udělali? Vynásobili jsme velikost obou množin. Měli jsme 3 dámy a 4 pány, celkový počet párů tak je 3 · 4 = 12. Proto kombinatorické pravidlo součinu. Pokud tak máme nějaké dvě množiny, ze kterých tvoříme dvojice, tak zkrátka jen vynásobíme počet prvků jedné množiny s počtem prvků druhé množiny.
Dále si můžete prohlédnout, že to skutečně platí. Následují všechny možnosti, jak můžeme 3 ženy a 4 muže uspořádat do párů. Každý řádek představuje možnosti pro jednu z žen a každý sloupec možnosti pro jednoho z pánů. Máme tak tři řádky a čtyři sloupce, celkem řádky · sloupce možností.
$$\begin{eqnarray} &&[Z_1, M_1], [Z_1, M_2], [Z_1, M_3], [Z_1, M_4], \\ &&[Z_2, M_1], [Z_2, M_2], [Z_2, M_3], [Z_2, M_4], \\ &&[Z_3, M_1], [Z_3, M_2], [Z_3, M_3], [Z_3, M_4] \end{eqnarray}$$
Řešené příklady
- Kolik existuje různých dvojciferných čísel? Jak takové dvojciferné číslo vypadá? Na prvním místě se vyskytuje jedna z číslic 1, …, 9, zatímco na druhém místě se už navíc může vyskytnout nula: 0, …, 9. V první množině tak máme 9 číslic, ve druhé 10. Použijeme kombinatorické pravidlo součinu a získáme konečný výsledek: 9 · 10 = 90.
- Kolik existuje různých trojciferných čísel, kde se žádná číslice nesmí vyskytnout dvakrát? Na prvním místě může být opět devět číslic, nulou číslo začínat nemůže. Na druhém místě mohou být všechny číslice včetně nuly, ale nesmí tam být číslice vysktující se na první pozici, takže od počtu deseti možných číslic odečteme jedničku (například pokud naše trojciferné číslo zrovna začíná čtyřkou, je jasné, že na druhé pozici se již čtyřka vyskytovat nemůže, protože by v celém čísle bylo dvakrát). Na třetím místě mohou být opět všechny číslice, ale nesmí tam číslice, která je na prvním nebo na druhém místě. Důvod je opět stejný. Pokud je na prvním místě číslice 4 a na druhém číslice 7, tak na třetí místo můžeme doplnit jednu číslici z {0, …, 9} ∖ {4, 7}. Od celkového počtu deseti číslic musíme odečíst dvojku. Nyní už jen vynásobíme 9 · 9 · 8 = 648. Celkový počet kombinací je 648.
- Dvakrát za sebou hodíme klasickou hrací kostkou. Kolik různých výsledků můžeme získat? V prvním hodu nám může na kostce padnout 6 různých výsledků. Ve druhém hodu také, takže celkový počet možností je 6 · 6 = 36.
- Dvakrát za sebou hodíme kostkou. Kolik různých výsledků můžeme získat, pokud nám v prvním hodu padlo sudé číslo? V prvním hodu padlo sudé číslo, tj. padlo jedno z čísel 2, 4, 6, což jsou celkem 3 možnosti. Ve druhém hodu už může padnout jakékoliv číslo, takže celkem máme 3 · 6 = 18 možností.