Kombinace

Technology

12 hours ago

Author

Kombinace je základní pojem z kombinatoriky. k-Členná kombinace z n prvků je skupina k prvků, vybraná z n různých prvků, u níž nezáleží na jejich pořadí. Od variace se liší tím, že je neuspořádaná.

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“.

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. +more 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ů: ab, ac, bc. Jedná se o kombinaci druhé třídy (tedy k=2) bez opakování. +more 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í. +more Pro počet trojic tedy platí.

C_3(3) = {3 \choose 3} = 1

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 n - k} = {{(n + k - 1)} \choose k} = {(n+k-1)! \over k!(n-1)!}

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. +more 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ů: aa, ab, bb. Jedná se o kombinaci druhé třídy (tedy k=2) s opakováním. +more Pro počet dvojic pak dostáváme.

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

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