Variace, permutace, kombinace
Kombinace
Kombinace se od variací liší tím, že nezáleží na pořadí vybraných prvků.
Definice
\(k\)-členná kombinace z \(n\) prvků je neuspořádaná \(k\)-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše jednou.
Abychom odlišili zápisy variací a kombinací, zapisujeme variace do kulatých závorek, např. \((c,a,b)\), a kombinace do složených závorek, např. \(\{e,f,g\}\).
Ukažme si rozdíl mezi tříčlennými variacemi ze čtyř prvků a tříčlennými kombinacemi ze čtyř prvků:
| Tříčlenné variace z prvků \(a,b,c,d\): | |||
|
\((a,b,c)\) \((a,c,b)\) \((b,a,c)\) \((b,c,a)\) \((c,a,b)\) \((c,b,a)\) |
\((a,b,d)\) \((a,d,b)\) \((b,a,d)\) \((b,d,a)\) \((d,a,b)\) \((d,b,a)\) |
\((a,c,d)\) \((a,d,c)\) \((c,a,d)\) \((c,d,a)\) \((d,a,c)\) \((d,c,a)\) |
\((b,c,d)\) \((b,d,c)\) \((c,b,d)\) \((c,d,b)\) \((d,b,c)\) \((d,c,b)\) |
| Tříčlenné kombinace z prvků \(a,b,c,d\): | |||
| \(\{a,b,c\}\) | \(\{a,b,d\}\) | \(\{a,c,d\}\) | \(\{b,c,d\}\) |
Každé tříčlenné kombinaci ze čtyř prvků odpovídá \(3!=6\) tříčlenných variací ze stejných čtyř prvků.
Obecně každé \(k\)-členné kombinaci z \(n\) prvků odpovídá \(k!\)\(k\)-členných variací ze stejných \(n\) prvků.
Odtud můžeme odvodit vztah mezi počtem \(k\)-členných kombinací z \(n\) prvků
\(K(k,n)\)
a počtem \(k\)-členných variací z \(n\) prvků
\(V(k,n)\):
\[V(k,n) = k! \cdot K(k,n)\].
Tento vztah můžeme dál rozepsat a vyjádřit počet \(k\)-členných kombinací
v závislosti na hodnotách \(k\) a \(n\):
Jak už bylo uvedeno výše, tříčlenné kombinace ze čtyř prvků jsou čtyři:
\(\{a,b,c\}\),
\(\{a,b,d\}\),
\(\{a,c,d\}\),
\(\{b,c,d\}\).
Zkusme jejich počet určit pomocí odvozeného vzorce:
Pro výpočet \(K(k,n)\) můžete využít následující skript:
| \(k=\) | ||
| \(n=\) | ||
| \(K(k,n)=\) | ||
Příklad
Ve třídě je \(26\) žáků. Kolika způsoby z nich lze vybrat dva zástupce třídy?
Řešení
\(K(2,26) = \dfrac{26!}{2! \cdot 24!} = 325\)
Kombinace a podmnožiny
Zůstaneme ještě chvíli u tříčlenných kombinací z prvků \(a,b,c,d\):
\(\{a,b,c\}\), \(\{a,b,d\}\), \(\{a,c,d\}\), \(\{b,c,d\}\).
Všimněte si, že tyto kombinace přesně odpovídají všem tříprvkovým podmnožinám množiny \(\{a,b,c,d\}\).Tato vlastnost platí obecně:
\(k\)-členná kombinace z \(n\) prvků je \(k\)-členná podmnožina množiny těmito \(n\) prvky určené.
Prázdnou množinu (\(k=0\)) lze z libovolné \(n\)-prvkové množiny vybrat vždy jen jediným způsobem, proto pro všechna \(n\), kde \(n\) je přirozené číslo, platí \(K(0,n) = 1\).
Příklad
Určete počet tříprvkových podmnožin množiny \(\{1,2,3,4,5,6,7,8,9,10\}\).
Řešení
Kombinační číslo
Kombinační číslo je symbol, který označuje počet \(k\)-členných kombinací z \(n\) prvků.
Definice
Počet \(K(k,n)\) všech \(k\)-členných kombinací z \(n\) prvků můžeme zapsat kombinačním číslem:
Při počítání s kombinačními čísly se často využívá následující vlastnost:
\[\displaystyle{{n \choose n-k} = {n \choose k}}\]
Odvození je snadné:
\[\displaystyle{{n \choose n-k} = \dfrac{n!}{(n-k)![n-(n-k)]!} = \dfrac{n!}{(n-k)!k!} = {n \choose k}}\]Příklad
U výtahu, do něhož můžou nastoupit nejvýše tři osoby, stojí \(5\) osob. Označme je \(a,b,c,d,e\). Sestavte všechny trojice osob, které mohou nastoupit, a vypište dvojice, které v daném případě nenastoupí.
Kliknutím na osobu před výtahem a ve výtahu se tyto dvě osoby vymění:
| Ve výtahu | Před výtahem |
|---|---|
| Adam, Bára, Cyril, David, Ema | Adam, Bára, Cyril, David, Ema |
Řešení
| Nastoupí | Zůstávají |
|---|---|
| \(\{a,b,c\}\) | \(\{e,d\}\) |
| \(\{a,b,d\}\) | \(\{c,e\}\) |
| \(\{a,b,e\}\) | \(\{c,d\}\) |
| \(\{a,c,d\}\) | \(\{b,e\}\) |
| \(\{a,c,e\}\) | \(\{b,d\}\) |
| \(\{a,d,e\}\) | \(\{b,c\}\) |
| \(\{b,c,d\}\) | \(\{a,e\}\) |
| \(\{b,c,e\}\) | \(\{a,d\}\) |
| \(\{b,d,e\}\) | \(\{a,c\}\) |
| \(\{c,d,e\}\) | \(\{a,b\}\) |
\(\displaystyle{{n \choose n-k} = {n \choose k}}\), tj. počet možností, jak vybrat tři lidi, kteří pojedou výtahem, je stejný, jako počet možností, jak vybrat dva lidi, kteří budou muset počkat: \(\displaystyle{{5 \choose 3} = {5 \choose 2}}\).
Další vlastnosti kombinačních čísel
Úlohy k tématu: kombinační čísla, kombinace
