Kombinace s opakováním

Poslední nástroj pro výpočet, který si představíme, jsou kombinace s opakování. Znovu, onen rozdíl oproti kombinacím bez opakování je, že dané prvky ze kterých vybíráme můžeme zvolit více-krát. Příkladem takové situace je, pokud máme například míčky různé barvy, které jsou navzájem nerozeznatelné a vybíráme z nich určitý stejný počet.

Kombinace s opakováním jsem zřejmě nejnáročnější koncept z těch, které si představíme. Motivace znovu zvolíme pomocí příkladu. Představme si, že máme neomezený počet míčku každé barvy a máme \(4\) různé barvy míčků a chceme z nich vybrat \(7\) míčků. Postup který zvolíme je, že si představíme v jedné řadě \(7\) koleček, které budou reprezentovat dané míčky a k tomu \(3\) přepážky, které vkládáme mezi tato kolečka a které rozdělují kolečka na \(4\) skupiny (v našem případě \(4\) barvy). Pak seřazení těchto koleček a přepážek udává konkrétní výběr daných barev. Například:

o o o | o o | o | o

znamená, že máme tři míčky první barvy, dva druhé, jeden třetí a jeden čtvrté. A například:

o | | o o o o | o o

znamená, že mám jeden míček první barvy, žádný druhé, čtyři třetí a dva čtvrté barvy.

Jak tedy vypočítat daný počet možností? Tak je zřejmé, že pro \(7\) míčků a 4 barvy máme dohromady \(7+3=10\) prvků k permutování (pro \(4\) barvy nám stačí \(3\) přepážky). Takže je to dohromady \(10!\) možností jak je přeřadit. Ale z permutací s opakováním víme, že pokud jsou od sebe kolečka nerozeznatelná a stejně tak i přepážky, tak musíme výsledek vydělit číslem \(7!\) za kolečka a \(3!\) za přepážky, tedy máme výsledek:

\(\dfrac{10!}{7! \cdot 3!}\)

Pokud tuto úvahu zobecníme na výběr \(k\) míčků \(n\) různých barev, tak máme dohromady \(n+k-1\) prvků k permutování a budeme dělit čísly \(k!\) a \((n-1)!\) a výpočet tedy bude:

\(K'(k,n)=\dfrac{(n+k-1)!}{k!\cdot (n-1)!}\)

což můžeme pomocí kombinačního čísla zapsat jako:

\(K'(k,n)=\begin{pmatrix}n+k-1\\k\end{pmatrix}\) \(=\begin{pmatrix}n+k-1\\n-1\end{pmatrix}=\dfrac{(n+k-1)!}{k!\cdot (n-1)!}\)

Komentáře

Ekaterina
02. 06. 2022 - 10:05

Dobrý den, pokud je to možné, ráda bych položila jednu otázku. Je třeba rozdělit 14 jablek mezi 3 kluky (je možné, aby jeden nebo dva z nich nedostal žádné jablko), a vím, že můžu použit vzorec \(\frac{(14+(3-1))!}{14!(3-1)!}\), ale jěště přemyšlím nad tím, že můžu umístit první přepážku na libovolné z 15 míst mezi jablky, a také druhou na libovolné z 15 míst, pak to vydělit dvěma, protože dát první přepážku před třetím jablkem a druhou před osmým je to samé, když dám druhou přepážku před třetím jablkem a první před osmým, tedy \({15*15\over 2}\). Mohl byste prosím říct, v čem je chyba?

Dominik Chládek
07. 06. 2022 - 22:18

Dobrý den, to mám hroznou radost, moc Vám děkuji za krásnou motivační zprávu, moc mě těší že Vám můžu pomáhat a že to funguje a líbí se Vám to :) moc přeji ať se daří ve studiu co nejlépe, hodně štěstí a děkuji že se koukáte! :)

Ekaterina
07. 06. 2022 - 10:47

Dobrý den, už to asi chapu, děkuji moc! Chci Vám také upřímně poděkovat za Vaše videa, už mám hodně Vašich kurzu za sebou, a jsou opravdu moc dobré! Vaše videa mi prostě nekutečně pomáhají. Jsem v prvním ročníku, a už jste mi několikrát zachránil život :D Velice se mi líbí to, že ukazujte, odkud se berou vzorce, se kterými pracujeme (třeba v analýze) a vůbec Váš lidský přístup :) Vždy velmi jasně vysvětlujete, a doufám, že budete točit dál! Pořád Vaše videa doporučuji svým kamarádům, jste pro mě hrdina :D Přeji Vám hodně štěsti!

Dominik Chládek
05. 06. 2022 - 21:41

To sice ano, ale vy říkáte že mezi každými oooooo máte dvě volná místa, ale ne jedno? Protože jak můžete někde zvolit dvě přepážky a přitom nemít místo? Není mi jasné kde brete 15*15 :)

Ekaterina
04. 06. 2022 - 19:32

Dobrý den, tak to by asi mělo znamenat, že prostřední kluk nedostane žádné jablko, ne? Třeba ooo||oooooooo bude znamenat, že první kluk dostal 3 jablka, druhý nedostal žádné, třetí dostal 11. Nebo ||oooooooooooooo bude znamenat, že první a druhý nedostali nic, a třetí dostal všechno.

Ekaterina
03. 06. 2022 - 10:32

Dobrý den, tak to by asi mělo znamenat, že prostřední kluk nedostane žádné jablko, ne? Třeba ooo||oooooooo bude znamenat, že první kluk dostal 3 jablka, druhý nedostal žádné, třetí dostal 11. Nebo ||oooooooooooooo bude znamenat, že první a druhý nedostali nic, a třetí dostal všechno.

Dominik Chládek
02. 06. 2022 - 23:23

Dobrý den, a jak byste popsal situaci, kdy vyberete na obě přepážky stejné místo? To tam pak najednou budou dvě místa? Nebo se přepážka sjednotí v jednu? :)

Přihlásit se pro komentář