Kombinace

Z Wikipedie, otevřené encyklopedie

Obsah

1 Definice
2 Kombinace bez opakování
- 2.1 Příklad
3 Kombinace s opakováním
- 3.1 Příklad
4 Podívejte se také na

[editovat] Definice

Kombinace $k$ -té třídy z $n$ prvků je skupina $k$ prvků vybraných z celkového počtu $n$ prvků, přičemž při výběru nezáleží na pořadí jednotlivých prvků. Rozlišujeme kombinace s opakováním a bez opakování.

[editovat] Kombinace bez opakování

Počet kombinací $k$ -té třídy z $n$ prvků bez opakování, tzn. žádný prvek výběru se nemůže opakovat, je

$C_k(n) = {n \choose k}$ ,

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

[editovat] Příklad

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$

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ů: $a b$ , $a c$ , $b c$ . 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ů: $a b c$ . 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$

[editovat] 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_k^{\prime}(n) = {{(n + k - 1)} \choose k}$

[editovat] Příklad

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_1^{\prime}(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ů: $a a$ , $a b$ , $b b$ . Jedná se o kombinaci druhé třídy (tedy $k = 2$ ) s opakování. Pro počet dvojic pak dostáváme

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