\begin{align} \end{align}

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\):

\[K(k,n) = \dfrac{1}{k!} \cdot V(k,n) = \dfrac{1}{k!} \cdot \dfrac{n!}{(n-k)!} = \dfrac{n!}{k! \cdot (n-k)!}\]
Počet \(K(k,n)\) všech \(k\)-členných kombinací z \(n\) prvků je \[K(k,n) = \dfrac{n!}{k!(n-k)!}\]

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:

\(K(3,4) = \dfrac{4!}{3! \cdot (4-3)!} = \dfrac{4!}{3! \cdot 1!} = 4\)

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í

Protože nezáleží na pořadí vybraných studentů, jde o dvoučlenné kombinace z \(26\) prvků. Jejich počet je

\(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í

Počet tříprvkových podmnožin desetiprvkové množiny je stejný jako počet tříčlenných kombinací z deseti prvků. Proto je hledaný počet \(K(3,10) = \dfrac{10!}{3! \cdot 7!} = 120\)

Kombinační číslo

Kombinační číslo je symbol, který označuje počet \(k\)-členných kombinací z \(n\) prvků.

Definice

Pro všechna celá nezáporná čísla \(n\), \(k\), \(k \leq n\), je \[\displaystyle{n \choose k} = \dfrac{n!}{k!(n-k)!}\]
Symbol \(\displaystyle{n \choose k}\)  čteme "\(n\) nad \(k\)".

Počet \(K(k,n)\) všech \(k\)-členných kombinací z \(n\) prvků můžeme zapsat kombinačním číslem:

\[K(k,n) = \displaystyle{n \choose k}\]

Při počítání s kombinačními čísly se často využívá následující vlastnost:

Pro všechna celá nezáporná čísla \(n\), \(k\), \(k \leq n\), platí
\[\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ýtahuPř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\}\)

Tento příklad názorně ilustruje výše uvedenou vlastnost
\(\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