Kombinace s opakováním

Pokud si vypíšeme všechny možnosti, zjistíme, že jich je 10:

Jak se početně dopočítáme k tomuto výsledku? Postup i pro další příklady si zkusíme odůvodnit. Každou kombinaci kuliček si zašifrujeme pomocí teček a čárek následovně:

Mysleme si, že máme tři hromádky – na jedné jsou červené kuličky, na druhé jsou modré a na poslední jsou žluté kuličky. Pro každou kombinaci zakreslíme pod příslušnou hromádku tolik teček, kolikrát se v dané kombinaci tento prvek vyskytuje. A pro rozlišení mezi sousedními hromádkami použijeme svislou čarou (mezi první a druhou přihrádkou a mezi druhou a třetí). Není-li kulička některé barvy v dané kombinaci, nebude pod touto hromádkou žádná tečka.

Dostaneme takové přiřazení:

$ \hspace{180px}$ $\quad \longrightarrow \quad \bullet\bullet\bullet \ | \ \ | \ $

$ \hspace{180px}$ $\quad \longrightarrow \quad \bullet\bullet \ | \ \bullet \ | \ $

$ \hspace{180px}$ $\quad \longrightarrow \quad \bullet\bullet \ | \ \ | \ \bullet $

$ \hspace{180px}$ $\quad \longrightarrow \quad \bullet \ | \ \bullet\bullet \ | \ $

$ \hspace{180px}$ $\quad \longrightarrow \quad \bullet \ | \ \bullet \ | \ \bullet $

$ \hspace{180px}$ $\quad \longrightarrow \quad \bullet \ | \ \ | \ \bullet\bullet$

$ \hspace{180px}$ $\quad \longrightarrow \quad \ | \ \bullet\bullet\bullet \ | \ $

$ \hspace{180px}$ $\quad \longrightarrow \quad \ | \ \bullet\bullet \ | \ \bullet$

$ \hspace{180px}$ $\quad \longrightarrow \quad \ | \ \bullet \ | \ \bullet\bullet$

$ \hspace{180px}$ $\quad \longrightarrow \quad \ | \ \ | \ \bullet\bullet\bullet$

Všimněte si, že takové přiřazení je jednoznačné – každé tří prvkové kombinaci můžeme jednoznačně přiřadit pětici skládající se z 3 teček a 2 svislých čar a obráceně.

Uvědomme si, že ačkoli nám u výběru kuliček nezáleželo na pořadí, u uspořádání teček a čar už jejich pořadí důležité je. Od kombinací s opakováním jsme jednoznačně přešli k permutacím s opakováním, jejichž počet už umíme vypočítat, dostáváme výsledek: $$ \dfrac{(3+2)!}{3!\cdot2!} = \dfrac{5!}{3!2!}=10$$

Poznámka: Na počet pětic složených ze tří teček a dvou čar se také můžeme dívat jako na výběr dvou míst z pěti, na kterých budou svislé čáry. Tento počet je tedy $ \dbinom{5}{2} $.

Stále máme tři hromádky - jedna červených, druhá modrých a poslední žlutých kuliček.

Počet kuliček příslušné barvy opět určíme tečkami a pro rozlišení jejich barev opět použijeme 2 svislé čáry.

Proč svislé čáry jsou právě dvě? Je to dáno počtem hromádek (různých prvků), pro rozdělení 3 různobarevných hromádek potřebujeme svislé čáry v počtu o jedno méně.

Příklad jednoho přiřazení:

$ \hspace{180px}$ $\quad \longrightarrow \quad \bullet \ | \ \ | \ \bullet\bullet\bullet$

Rozmísťujeme 4 tečky a 2 svislé čáry, kde záleží na jejich pořadí, dostáváme výsledek: $$ \dfrac{(4+2)!}{4!\cdot2!} = \dfrac{6!}{4!2!}=15\qquad \qquad \left[ = \dbinom{6}{2} \right] $$

Nyní dostáváme čtyři hromádky - na jedné jsou červené kuličky, na druhé jsou modré, na třetí žluté a na poslední zelené kuličky. Zašifrováváme je stejným způsobem jako v předešlých dvou příkladech. Pomocí teček a svislých čar. Kolik bude nyní teček a čar? Vybíráme 3 kuličky, proto budou 3 tečky. Máme 4 různé barvy, proto budou 3 svislé čáry.

Příklad jednoho přiřazení:

$ \hspace{180px}$ $\quad \longrightarrow \quad \ | \ \bullet \ | \ \bullet | \ \bullet$

Rozmísťujeme 3 tečky a 3 svislé čáry, kde záleží na jejich pořadí, dostáváme výsledek: $$ \dfrac{(3+3)!}{3!\cdot3!} = \dfrac{6!}{3!3!}=20\qquad \qquad \left[ = \dbinom{6}{3} \right] $$

$$ K'(k,n) = P'(k, n-1) \qquad \text{nebo-li} \qquad \dbinom{n+k-1}{k} = \dfrac{[k + (n-1)]!}{k!(n-1)!} $$

Odvození:

Rozepsáním podle definic permutací s opakováním, kombinací s opakováním a kombinačního čísla dostáváme:

$ K'(k,n) = \dbinom{n+k-1}{k} = \dfrac{(n + k - 1)!}{k![(n+k-1)-k]!} = \dfrac{(n + k -1)!}{k!(n-1)!} $

$ P'(k, n-1) = \dfrac{[k + (n - 1)]!}{k!(n-1)!} = \dfrac{(n + k - 1)!}{k!(n-1)!} $

Dohromady: $ K'(k,n) = \dfrac{n + k - 1)!}{k!(n-1)!} = P'(k, n-1)$.

Vybíráme 3 číslice z deseti, číslice se mohou opakovat a nezáležím nám na jejich pořadí. (3 tečky a 9 svislých čar) $$\dbinom{3+10-1}{3} = \dbinom{12}{3} \qquad [= \dfrac{12!}{3!9!} = 220]$$

Krychle má všechny délky hran stejně dlouhé, my máme k dispozici 10 různých číslic, proto je $10$ krychlí.

a) Vybíráme 4 koláče ze 3 různých druhů: $$\dbinom{4+(3-1)}{4}=\dbinom{6}{4} \qquad [=\dfrac{6!}{4!2!}=15] $$

b) V tomto případě si Matěj nemůžeme vybrat 6 koláčů stejného druhu. Od počtu všech kombinací odečteme počet těch kombinací, kde jsou všechny koláče stejné, a dostaneme požadovaný výsledek: $$\dbinom{6 + (3-1)}{6} - 3 = 28 - 3 = 25 $$

a) Vybíráme 15 pohlednic z 10 různých druhů: $$\dbinom{15+(10-1)}{15}=\dbinom{24}{15} \qquad [=\dfrac{24!}{15!9!}=1307504] $$

b) V tomto případě nemůžeme vybrat 51 pohlednic jednoho druhu. Proto odečteme počet případů, kdy jsou všechny pohlednice stejné, a dostaneme náš výsledek: $$\dbinom{51+(10-1)}{51}-10=\dbinom{60}{51}-10 \qquad [=14783142660-10=14783142650] $$

c) Vybíráme 8 různých pohlednic, tzn. že se prvky nemohou opakovat: $$\dbinom{10}{8} \qquad [= 45] $$

$$ \dbinom{6}{3} \qquad [=20] $$

A) $ \dbinom{6}{3} - 3 \qquad [=20-3=17] $

B) $ \dbinom{5}{2} \qquad [=10] $

a) $ \dbinom{7}{4} \qquad [=35] $

b) $ \dbinom{11}{4} \qquad [=330] $

$$ \dbinom{8}{3} \qquad [=56] $$

$$ \dbinom{5}{3} - 1 \qquad [=10-1=9] $$

a) Uvědomme si, že tentokrát rozdělující svislé čáry dáváme mezi děti. Proto výsledek je $$ \dbinom{15 + (6-1)}{15}=\dbinom{20}{15} \qquad [=15 504] $$

b) Nejprve dáme každému dítěti jeden míček a poté rozdělíme zbylých devět míčků. $$ \dbinom{9 + (6-1)}{9}=\dbinom{14}{9} \qquad [=2002] $$

Nalezneme nejprve počet všech rozdělení hrušek mezi 3 osoby, podobně jako v předchozím příkladu, zjistíme, že jich je $ \dbinom{7+(3-1)}{7} = \dbinom{9}{7} $. A poté počet všech rozdělení jablek, těchto je $ \dbinom{5+(3-1)}{5} = \dbinom{7}{5} $.

Podle pravidla součinu je možné rozdělení obou druhů ovoce provést $ \dbinom{9}{7} \cdot \dbinom{7}{5} = 756$ způsoby.

Nákup káv je možný $ \dbinom{16}{12} [=1820] $ způsoby.

Požadujeme-li, aby v nákupu bylo alespoň po dvou balíčcích každého druhu kávy a kávy je pět druhů, deset balíčků je už určeno. Stačí tedy vybrat jen dva balíčky kávy, takových možností je $ \dbinom{6}{2} [=15] $ možností.

A) Nesmí-li žádná přihrádka zůstat prázdná, tzn. že v každé bude právě jedna koule. Stačí vybrat 2 přihrádky z devíti, v nichž budou černé koule. Do zbylých přihrádek je rozmístění bílých koulí jednoznačné. $$ \dbinom{9}{2} \qquad [=36] $$

B) Rozmístíme bílé koule a poté černé koule: $$ \dbinom{15}{7} \cdot \dbinom{10}{2} \qquad [=289575] $$

Poznámka: Všimněte si, že v případě A) se jednalo o kombinace bez opakování. V přihrádce mohla být pouze jedna koule, tato přihrádka se tedy nemohla opakovat ve výběru pro umístění další koule. V případě b) v přihrádce mohlo být více koulí a mohli jsme ji tedy použít opakovaně pro výběr umístění dalších koulí.

A) $ \dbinom{26}{15} \qquad [=7726160] $

B) $ \dbinom{18}{7} \qquad [=31824] $

C) $ \dbinom{12}{7} \qquad [=792] $

Bc. Monika Stančíková |
ÚMS, Přírodovědecká fakulta, Masarykova univerzita |
Návrat na úvodní stránku webu, přístupnost |

| Šablonu poskytlo:
| Servisní středisko pro e-learning na MU
| Fakulta informatiky Masarykovy univerzity, 2015

Nahoru