Variace, permutace a kombinace s opakováním

Kombinace s opakováním

Příklad

Určete, kolika způsoby je možné rozmístit tři stejné kuličky do čtyř krabiček.

Řešení

Třikrát vybíráme jednu ze čtyř krabiček, do které umístíme kuličku; jde tedy o tříčlenné kombinace s opakováním ze čtyř prvků (\(k=3\) ,\(n=4\) ).
V následující tabulce jsou vypsané všechny možnosti, jak se dají tři kuličky rozmístit do čtyř krabiček, a vedle každé možnosti je odpovídající symbolický zápis, ze kterého později odvodíme vzorec pro výpočet počtu těchto možností. V tomto symbolickém zápise zůstává pro kuličku stejný symbol jako v tabulce (•); svislá čára (|) označuje oddělení dvou sousedních krabiček. Těchto symbolů je pro \(n\)krabiček potřeba \(n-1\) , v našem případě tedy \(4-1=3\) , protože u krajních krabiček stačí oddělení jen z jedné strany. Tak například symbolický zápis pro jednu kuličku v první krabičce a dvě kuličky ve třetí krabičce (druhá a čtvrtá krabička zůstane prázdná) je  • | | • • | .

		Číslo krabičky					Symbolický zápis
		1	2	3	4
1		• • •					• • • | | |
2			• • •				| • • • | |
3				• • •			| | • • • |
4					• • •		| | | • • •
5		• •	•				• • | • | |
6		• •		•			• • | | • |
7		• •			•		• • | | | •
8		•	• •				• | • • | |
9			• •	•			| • • | • |
10			• •		•		| • • | | •
11		•		• •			• | | • • |
12			•	• •			| • | • • |
13				• •	•		| | • • | •
14		•			• •		• | | | • •
15			•		• •		| • | | • •
16				•	• •		| | • | • •
17		•	•	•			• | • | • |
18		•	•		•		• | • | | •
19		•		•	•		• | | • | •
20			•	•	•		| • | • | •

Tři stejné kuličky je možné rozmístit do čtyř krabiček dvaceti způsoby.

V tomto případě bylo ještě možné vypsat všechny způsoby, jak tři kuličky rozmístit do čtyř krabiček, a potom je jednoduše spočítat. Pro větší čísla je ale takový postup nepoužitelný. K odvození výpočtu pro obecné \(n\) a \(k\) využijeme zmíněný symbolický zápis rozdělení kuliček.
Všimněte si, že ke každému rozdělení kuliček do krabiček je přiřazen právě jeden symbolický zápis. Obráceně platí, že každé šestici, ve které se vyskytují tři znaky • a tři znaky |, je přiřazeno také právě jedno rozdělení kuliček do krabiček. Vyzkoušejte si, jestli rozumíte tomuto přiřazení správně:

Jestliže je tedy toto přiřazení vzájemně jednoznačné, odpovídá také počet různých šestic tří symbolů • a tří symbolů | počtu všech možných rozmístění tří kuliček do čtyř krabiček. Přitom počet uvedených šestic symbolů umíme určit: jedná se o permutace s opakováním ze dvou prvků (•, |), kde se první prvek (•) opakuje třikrát a stejně tak i druhý prvek (|) se zde opakuje třikrát. Počet takových permutací s opakováním je \[P'(3,3) = \dfrac{(3+3)!}{3! 3!} = \dfrac{720}{6 \cdot 6} = 20,\] což odpovídá počtu řádků výše uvedené tabulky.

Zobecníme-li úlohu tak, že budeme hledat počet způsobů, jak rozmístit \(k\) stejných kuliček do \(n\)krabiček, dala by se tato rozmístění šifrovat \((k+n-1)\)-ticemi, ve kterých se symbol • vyskytuje \(k\)-krát (\(k\) kuliček) a symbol | \((n-1)\)-krát (\(n-1\) oddělení mezi \(n\) krabičkami). Počet takových \((k+n-1)\)-tic odpovídá počtu permutací dvou prvků s opakováním, kde se první prvek opakuje \(k\)-krát a druhý \((n-1)\)-krát: \[P'(k, n-1) = \dfrac{(k+n-1)!}{k! (n-1)!} = \dfrac{(n+k-1)!}{k! (n-1)!} = \displaystyle{n+k-1 \choose k}\] Protože tento počet \((k+n-1)\)-tic \(k\) znaků • a \((n-1)\) znaků | je stejný jako počet různých rozmístění \(k\) kuliček do \(n\) přihrádek, dostáváme vzorec pro \(k\)-členné kombinace s opakováním z \(n\) prvků:

\[K'(k,n) = P'(k, n-1) = \displaystyle{n+k-1 \choose k}\].

Příklad

Určete, kolika způsoby je možné rozmístit sedm stejných kuliček do tří krabiček.

Řešení

Sedmkrát vybíráme jednu ze tří krabiček, do které umístíme kuličku; jde tedy o sedmičlenné kombinace s opakováním ze tří prvků (\(k=7\), \(n=3\)).

\(K'(7,3) = \displaystyle{3+7-1 \choose 7} = \displaystyle{9 \choose 7} = \dfrac{9!}{7! 2!} = 36\)

Příklad

Kolika způsoby lze rozdělit \(15\) bonbónů mezi \(10\) dětí?

Řešení

Patnáctkrát vybíráme jedno z deseti dětí, kterému dáme bonbón; jde tedy o patnáctičlenné kombinace s opakováním z deseti prvků (\(k=15\), \(n=10\)).

\(K'(15,10) = \displaystyle{10+15-1 \choose 15} = \displaystyle{24 \choose 15} = \dfrac{24!}{15! 9!} = 1\,307\,504\)

Příklad

Určete počet všech trojúhelníků, z nichž žádné dva nejsou shodné a jejichž každá strana má velikost vyjádřenou jedním z čísel \(4, 5, 6, 7\) .

Řešení

Tři čísla \(a, b, c\) mohou být velikosti stran trojúhelníku, pokud platí \(a+b > c\), \(a+c > b\), \(b+c > a\). Tuto podmínku splňuje každá trojice sestavená z čísel \(4, 5, 6, 7\): vezmeme dvě nejmenší možná čísla (tj. \(4\) a \(4\)) a porovnáme jejich součet s největším možným číslem (tj. \(7\)). Protože \(4+4 > 7\), trojúhelníková nerovnost platí pro krajní případ, a proto platí i pro všechny ostatní případy.
Příklad se tak zjednodušil na hledání počtu neuspořádaných trojic sestavených z čísel \(4, 5, 6, 7\), tedy na určení počtu tříčlenných kombinací s opakováním ze čtyř prvků (\(k=3\), \(n=4\)).

\(K'(3,4) = \displaystyle{4+3-1 \choose 3} = \displaystyle{6 \choose 3} = \dfrac{6!}{3! 3!} = 20\)

Několik úloh ke kombinacím s opakováním