Kombinace s opakováním

Kapitoly: Kombinatorika, Variace, Permutace, Kombinace, Variace s opakováním, Kombinace s opakováním

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

  1. 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. $$

Zdroje a další čtení