Kombinace

Kombinace je neuspořádaná k-tice vytvořená z celkového počtu n prvků, přičemž nezáleží na pořadí vybraných prvků. Rozlišujeme kombinace s opakováním a bez opakování. Pro výpočet hodnoty je používán faktoriál. Kombinace jsou základním pojmem z kombinatoriky. Variace se odlišují tím, že u nich je výběr uspořádaný (záleží na pořadí vybraných prvků).

Kombinace bez opakování

Počet kombinací $k$-té třídy z $n$-prvků bez opakování, neuspořádaných $k$-tic vybraných z těchto prvků tak, že se v ní každý vyskytuje nejvýše jednou, je:

$C(k,n)={n \choose k}={n! \over k!(n-k)!}$

kde symbol ${n \choose k}$ představuje kombinační číslo „n nad k“.

Někdy se používá zápis s indexem nebo místo písmene $C$ písmeno $K$, takže následující zápisy jsou rovnocenné: $C(k,n)=C_{k}(n)=K_{k}(n)$.

Odvození výpočtu

Počet kombinací zde odvodit tak, že počet všech variací vydělíme $k!$ (tj. počtem permutací každé $k$-tice), protože všechny možné permutace vybraných prvků v kombinacích nepotřebujeme:

$C(k,n)={V(k,n) \over k!}={n! \over (n-k)!}\cdot {1 \over k!}={n! \over (n-k)!\cdot k!}$

Kombinace s opakováním

Počet kombinací $k$-té třídy z $n$ prvků s opakováním, tzn. každý prvek se ve výběru může objevit vícekrát, je určen vztahem:

$C^{\prime }(k,n)={{(n+k-1)} \choose n-1}={{(n+k-1)} \choose k}={(n+k-1)! \over k!(n-1)!}$

Vysvětlení

Kombinace bez opakování

Mějme skupinu tří prvků $a,b,c$, tzn. $n=3$. Chceme-li z těchto prvků vybrat vždy jen jeden prvek, můžeme to udělat třemi možnými způsoby, tzn. vybereme $a$ nebo $b$ nebo $c$. Jedná se o kombinaci první třídy, tzn. $k=1$, a tedy počet výběrů je roven:

$C(1,3)={3 \choose 1}={3! \over {1!\cdot (3-1)!}}={3\cdot 2! \over 2!}=3$

Chceme-li z uvedené trojice prvků vybrat vždy dva, přičemž nám nezáleží na pořadí a žádný prvek nemůžeme vybrat vícekrát, můžeme získat následující dvojice prvků: $ab$, $ac$, $bc$. Jedná se o kombinaci druhé třídy (tedy $k=2$) bez opakování. Pro počet dvojic pak dostáváme

$C(2,3)={3 \choose 2}=3$

Pokud chceme z uvedené trojice prvků vybrat vždy tři, přičemž nám nezáleží na pořadí a žádný prvek nemůžeme vybrat vícekrát, můžeme získat pouze jedinou trojici prvků: $abc$. Jedná se o kombinaci třetí třídy (tedy $k=3$) bez opakování. Pro počet trojic tedy platí

$C(3,3)={3 \choose 3}=1$

Kombinace s opakováním

Mějme skupinu dvou prvků $a,b$, tzn. $n=2$. Chceme-li z těchto prvků vybrat vždy jen jeden prvek, můžeme to udělat dvěma možnými způsoby, tzn. vybereme $a$ nebo $b$. Jedná se o kombinaci první třídy, tzn. $k=1$, a tedy počet výběrů je roven:

$C^{\prime }(1,2)={{(2+1-1)} \choose 1}={2 \choose 1}=2$

Je vidět, že u kombinací první třídy není třeba rozlišovat, zda jsou s opakováním nebo bez opakování.

Chceme-li z uvedené dvojice prvků vybrat vždy dva, přičemž nám nezáleží na pořadí a každý prvek můžeme vybrat vícekrát, můžeme získat následující dvojice prvků: $aa$, $ab$, $bb$. Jedná se o kombinaci druhé třídy (tedy $k=2$) s opakováním. Pro počet dvojic pak dostáváme:

$C^{\prime }(2,2)={{(2+2-1)} \choose 2}={3 \choose 2}=3$

Obdobně bychom dostali $C^{\prime }(3,2)={{(2+3-1)} \choose 3}={4 \choose 3}=4$, atd.

Příklady

Příklad 1

Jaký je počet možných různých tahů Sportky, kde se z celkem 49 čísel náhodně vybírá 6 čísel (tj. kolik různých sázek lze vytvořit)?

Nezáleží na výsledném pořadí vylosovaných čísel, a proto se jedná o kombinace. Protože vylosované číslo už nemůže být znovu vylosováno, jsou to kombinace bez opakování:

$C(6,49)={49 \choose 6}={49! \over {6!\cdot (49-6)!}}={{49\cdot 48\cdot 47\cdot 46\cdot 45\cdot 44\cdot 43!} \over {720\cdot 43!}}={{49\cdot 48\cdot 47\cdot 46\cdot 45\cdot 44} \over {720}}=13~983~816$

Celkem je možných téměř 14 miliónů různých sázek, přičemž hlavní výhru (tj. uhodnout všechna vsazená čísla) může jen jedna z těchto všech možností.

Příklad 2

Kolik je různých možností nákupu 5 porcí zmrzliny, když je na výběr z 10 druhů?

Nezáleží na výsledném pořadí vylosovaných čísel, a proto se jedná o kombinace. Protože je možné koupit více porcí stejného druhu, jsou to kombinace s opakováním:

$C^{\prime }(5,10)={(10+5-1) \choose 5}={14! \over {5!\cdot (10-1)!}}={14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9! \over 5!\cdot 9!}={240~240 \over 120}=2~002$

Celkem je 2002 možností nákupu.

Odkazy

Literatura

• Odmaturuj z matematiky. [s.l.]: Didaktis, 2003 (druhé opravené vydání). ISBN 80-86285-97-9. Kapitola 35.Kombinatorika. 

Související články

• Permutace
• Variace

Externí odkazy

• Obrázky, zvuky či videa k tématu kombinace na Wikimedia Commons
• Téma Kombinace ve Wikicitátech
• Slovníkové heslo kombinace ve Wikislovníku

Autoritní data	PSH: 7156