Kombinace s opakováním
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
Kombinace s opakováním se podobají klasickým kombinacím, pouze dovolujeme, aby se mohly prvky z nosné množiny M opakovat.
Definice a vzorec
Začneme nějakým hezkým příkladem: přijdete do obchodu a chcete si na čundr koupit dvanáct lahvových piv. V regálu mají celkem čtyři různé lahváče. Nyní máte několik možností, jak lahváče koupit — můžete například koupit 5 Plzní, 2 Gambrinusy a 1 Staropramen nebo můžete koupit od každého výrobce právě dva lahváče. Kolik celkem existuje různých možností, jak lahváče koupit, abyste jich měli právě dvanáct?
Máme tak základní množinu M = {Plzeň, Gambrinus, Staropramen, Kozel} a ptáme se, kolik existuje k-tic, kde k = 12, které obsahují prvky z množiny M a u kterých nezáleží na pořadí?
Odvození vzorce už je poměrně složitější než u ostatních kombinatorických úloh. Jako první si náš nákup představíme jako posloupnost nul a jedniček tak, že počet jedniček odpovídá počtu koupených lahváčů daného výrobce a nula odděluje jednotlivé výrobce. Takže 111011101111101 nám říká, že jsme koupili tři Plzně (první tři 1), pak tři Gambrinusy (0 je oddělovač, další tři 1), pak pět Staropramenů (0 oddělovač a pak pět 1) a nakonec jednoho Kozla. Celý princip zobrazuje následující obrázek:
$$ \underbrace{111}_{Plz}0\underbrace{111}_{Gam}0\underbrace{11111}_{Star}0\underbrace{1}_{Koz} $$
Pokud bychom chtěli koupit 6 Plzní, 4 Gambrinusy, 2 Kozly a žádný Staropramen, vypadala by posloupnost takto:
$$ \underbrace{111111}_{Plz}0\underbrace{1111}_{Gam}00\underbrace{11}_{Koz} $$
Všimněme si, že délka této posloupnosti je vždy rovna 15 — musí tam být 12 jedniček, abychom nakoupili celkem 12 piv. A musí tam být tři oddělovače, abychom byli schopni oddělit čtyři různé výrobce. Zbývá tak vypočítat, kolik celkem existuje takových posloupností o délce 15, které obsahují právě tři nuly?
Stačí nám vypočítat umístění nul — ve chvíli, kdy mezi 12 jedniček rozmístíme 3 nuly, máme nějakou platnou kombinaci piv. Jinými slovy: máme celkem 15 chlívků a my 3 z nich musíme obsadit nulou. Zbylé chlívky automaticky obsadíme jedničkami.
Tohle už je jednoduchá úloha na kombinace bez opakování. 15 chlívků očíslujeme čísly {1, …, 15} a nyní z této množiny vybíráme vždy trojice čísel, čímž dostaneme tři indexy, kam umístíme nulu. Např. pro kombinaci {2, 4, 7} bychom získali posloupnost: 101011011111111. Na 2., 4. a 7. místě je nula, zbytek jsou jedničky. Existuje tak celkem
$$ {15\choose3} = 455 $$
různých způsobů, jak do 15 chlívků rozmístit nuly a tím pádem i 455 různých možností, jak nakoupit 12 piv, máme-li čtyři různé druhy piv.
Předchozí úvahu můžeme zobecnit. Pokud máme množinu prvků M o velikosti n a vybíráme z ní k-tice, přičemž jednotlivé prvky se mohou opakovat, pak skládáme posloupnost nul a jedniček o délce n + k − 1 (k jedniček a n − 1 nul) a zjišťujeme, na kolik pozic můžeme umístit n − 1 nul, takže počet kombinací s opakováním, označíme C'(k, n), je roven
$$ C'(k, n) = {n+k-1 \choose n-1} = {n+k-1\choose k}. $$
Poslední úpravu jsme si mohli dovolit díky základním vztahům mezi kombinačními čísly.
Řešené příklady
- Kolika způsoby lze rozdělit 20 volných vstupenek na premiéru Babovřesek mezi 10 důchodkyň? To je příklad na kombinace s opakováním, protože jedna důchodkyně může dostat více, potenciálně všechny, volné vstupenky. Musíme si jen správně uvědomit, co je n a co k. Ve skutečnosti vybíráme 20členné kombinace z 10 důchodkyň, jinými slovy vytváříme posloupnost nul a jedniček tak, že posloupnost má délku 29, obsahuje 20 jedniček a 9 nul. Takže n = 10, k = 20 Dostáváme výsledek:
$$ C'(10, 20) = {10 + 20 - 1 \choose 20} = 10{,}015,005. $$