PRUMYSL.CZ KONSTRUKTER.CZ 3D-TISK.CZ MATEMATIKA.CZ NOVAMEDIA.CZ

Kombinace s opakováním

Zobrazit kapitoly článku
  1. Kombinatorika
  2. Variace
  3. Permutace
  4. Kombinace
  5. Variace s opakováním
  6. 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í #

 

Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace