Kombinatorika
a pravděpodobnost

KOMBINATORIKA

L24: Kombinace s opakováním

<< Předchozí lekce | Seznam lekcí | Další lekce >>

V jedné z předchozích lekcí jsme se již seznámili s kombinací bez opakování, což je neuspořádaná k-tice z n prvků, která je sestavena tak, že každý se v ní vyskytuje právě jednou. V případě kombinací s opakováním budeme tentokrát sestavovat k-tice z n prvků tak, že se dané prvky budou moci opakovat.

Kombinace s opakováním:
k-členná kombinace s opakováním z n prvků je neuspořádaná k-tice sestavená z těchto prvků tak, že každý prvek se v ní vyskytuje nejvýše k-krát.
Příklad L24.01:

V krabici je 10 zelených, 10 modrých a 10 červených kuliček. Z krabice současně vytáhneme 3 kuličky. Kolik různých barevných kombinací můžeme získat? Vypiště všechny možnosti.

Řešení

Výběr 3 kuliček může skončit 10 různými výsledky.

Počet všech k-prvkových kombinací s opakováním z n prvků:
Počet všech k-prvkových kombinací s opakováním z n prvků je: $${K`(k, n) = \binom{n + k - 1}{k}}$$
Příklad L24.02:

V krabici je 10 zelených, 10 modrých a 10 červených kuliček. Z krabice současně vytáhneme 3 kuličky. Kolik různých barevných kombinací můžeme získat? Určete pomocí vzorce pro výpočet počtu kombinací s opakováním.

Řešení

Máme tvořit trojice ze tří barev. Bude se tedy jednat o kombinace s opakováním třetího řádu ze tří prvků. $${K`(3, 3) = \binom{3 + 3 - 1}{3} = \binom{5}{3} = \frac{5!}{3! \cdot (5 - 3)!} = \frac{5!}{3! \cdot 2!} = 10}$$

Výběr 3 kuliček může skončit 10 různými výsledky.

Příklad L24.03:

Kolik různých součtů můžeme získat, vybíráme-li 3 sčítance z čísel 2, 23, 123 a 1000?

Řešení

Protože je součet komutativní operace, nebude záviset na pořadí výběru sčítanců. Bude se tedy jednat o kombinaci s opakováním. Protože vybíráme 3 prvky ze 4, bude to kombinace bez opakování 3. řádu ze 4 prvků. $${K`(3, 4) = \binom{4 + 3 - 1}{3} = \binom{6}{3} = \frac{6!}{3! \cdot (6 - 3)!} = \frac{6!}{3! \cdot 3!} = 20}$$

Pokud vybírýme 3 sčítance z čísel 2, 23, 123 a 1000, můžeme získat 20 různých součtů.

Příklad L24.04:

Máme balíček 52 karet, kde jsou 4 barvy karet (srdce, káry, kříže, piky) a pro každou barvu existuje celkem 13 různých karet (2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A). Kolik různých čtveřic karet můžeme získat, budeme-li brát v úvahu pouze barvu karty?

Řešení

Ve vybrané skupině nebude záležet na pořadí. Je tedy třeba zjistit počet kombinací s opakováním čtvrtého řádu ze čtyř prvků. $${K`(4, 4) = \binom{4 + 4 - 1}{4} = \binom{7}{4} = \frac{7!}{4! \cdot (7 - 4)!} = \frac{7!}{4! \cdot 3!} = 35}$$

Můžeme získat 35 různých čtveřic karet.

Příklad L24.05:

Kolika způsoby můžeme umístit 5 stejných koulí do 3 různých krabic?

Řešení

Máme 5 koulí a každé můžeme přiřadit číslo krabice. Tím, že jsou všechny stejné, není nutné řešit jejich pořadí. Bude se tedy jednat o kombinaci s opakováním 5. řádu ze tří prvků: $${K`(5, 3) = \binom{3 + 5 - 1}{5} = \binom{7}{5} = \frac{7!}{5! \cdot (7 - 5)!} = \frac{7!}{5! \cdot 2!} = 21}$$

Výsledek můžeme ověřit jednoduchou tabulkou:

Příklad L24.06:

Máme za úkol rozdělit 14 čokolád mezi 10 dětí.
a) Kolik možností rozdělení čokolád máme, pokud nebudeme klást žádné omezení?
b) Kolik možností rozdělení čokolád máme, pokud má každé dítě dostat alespoň jednu čokoládu?
c) Kolik možností rozdělení čokolád máme, pokud má každé dítě dostat alespoň jednu čokoládu a nejmladší dítě má dostat minimálně 2 čokolády?

Řešení

a)

V tomto případě tvoříme kombinace s opakováním 14. řádu z 10 prvků. $${K`(14, 10) = \binom{10 + 14 - 1}{14} = \binom{23}{14} = \frac{23!}{14! \cdot (23 - 14)!} = \frac{23!}{14! \cdot 9!} = 817~190}$$

b)

V tomto případě každý dostane jednu čokoládu a budeme dělit už jen zbylé 4, tvoříme tedy kombinace s opakováním 4. řádu z 10 prvků. $${K`(4, 10) = \binom{10 + 4 - 1}{4} = \binom{13}{4} = \frac{13!}{4! \cdot (13 - 4)!} = \frac{13!}{4! \cdot 9!} = 715}$$

c)

V tomto případě každý dostane jednu čokoládu a nejmladší dítě dvě. Následně budeme dělit už jen zbylé 3, tvoříme tedy kombinace s opakováním 3. řádu z 10 prvků. $${K`(3, 10) = \binom{10 + 3 - 1}{3} = \binom{12}{3} = \frac{12!}{3! \cdot (12 - 3)!} = \frac{12!}{3! \cdot 9!} = 220}$$

Kontrolní otázky
  1. Co je to "kombinace s opakováním"?
  2. Pomocí jakého vzorce vypočítáme počet kombinací s opakováním?
  3. Ve skladu dodavatele IT je 6 stejných notebooků, které mají být rozvezeny do 4 prodejen. Nezáleží na pořadí prodejen a může nastat situace, že některá prodejna neobdrží žádný notebook, nebo některá prodejna obdrží všechny. Kolikati způsoby lze toto zboží rozvézt?
Řešení
  1. k-členná kombinace s opakováním z n prvků je neuspořádaná k-tice sestavená z těchto prvků tak, že každý prvek se v ní vyskytuje nejvýše k-krát.
  2. $${K`(k, n) = \binom{n + k - 1}{k}}$$
  3. ${K`(6, 4) = 84}$

<< Předchozí lekce | Seznam lekcí | Další lekce >>

Copyright © 2014 Ing. Michal Heczko