\begin{align} \end{align}

Kombinační čísla

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\)".

Příklady

\(\displaystyle{7 \choose 5} = \dfrac{7!}{5!(7-2)!} = \dfrac{7!}{5! 2!} = 21\)
\(\displaystyle{0 \choose 0} = \dfrac{0!}{0! 0!} = \dfrac{1}{1 \cdot 1} = 1\)

Určíme hodnoty několika speciálních případů kombinačních čísel:

\(k=0\)

\(\displaystyle{n \choose 0} = \dfrac{n!}{0! (n-0)!} = \dfrac{n!}{n!} = 1\)


\(k=n\)

\(\displaystyle{n \choose n} = \dfrac{n!}{n! (n-n)!} = \dfrac{n!}{n!} = 1\)


\(k=1\)

\(\displaystyle{n \choose 1} = \dfrac{n!}{1! (n-1)!} = n\)
Pro všechna přirozená čísla \(n\) platí \[\displaystyle{n \choose 0} = \displaystyle{n \choose n} = 1\]\[\displaystyle{n \choose 1} = n\]

Vlastnosti kombinačních čísel

Věta

Pro všechna celá nezáporná čísla \(n\), \(k\), \(k \leq n\), platí \[\displaystyle{n \choose n-k} = \displaystyle{n \choose k}\]

Důkaz:

\[\displaystyle{n \choose n-k} = \dfrac{n!}{(n-k)! \left[ n-(n-k) \right]!} = \dfrac{n!}{(n-k)! k!} = \displaystyle{n \choose k}\]

Tato vlastnost matematicky popisuje jednoduchý fakt: Chceme-li vybrat \(k\)-prvkovou podmnožinu \(n\)-prvkové množiny, zbyde vždy \(n-k\) nevybraných prvků. Rozhodneme-li se tedy vybrat \(n-k\) prvků, které do hledané podmnožiny nezařadíme, počet možností, jak je vybrat, bude stejný jako při přímém výběru \(k\) prvků.

Příklad

Mezi šest dětí chceme rozdělit \(2\) oranžová a \(4\) zelená trička. Určete počet možností, jak to udělat.

Řešení

První možnost: Určíme počet možností, jak vybrat dvě děti, které dostanou oranžová trička; ostatní čtyři dostanou zelená trička.
Druhá možnost: Určíme počet možností, jak vybrat čtyři děti, které dostanou zelená trička; ostatní dvě dostanou oranžová trička.

\(\displaystyle{6 \choose 2} = \displaystyle{6 \choose 4} = \dfrac{6!}{2! 4!} = \boldsymbol{15}\)

Najděte všechny možnosti, jak rozdělit trička:

Vyberte tričko a potom ho kliknutím na jméno přiřaďte některému z dětí.

zelené tričko oranžové tričko Anna, Bára, Cyril, David, Eva, Filip

Přidat rozdělení do tabulky / Smazat změny

AnnaBáraCyrilDavidEvaFilip

Věta

Pro všechna celá nezáporná čísla \(n\), \(k\), \(k < n\), platí \[\displaystyle{n \choose k} + \displaystyle{n \choose k+1} = \displaystyle{n+1 \choose k+1}\]
Důkaz vychází z definice kombinačního čísla. Zobrazit

Příklad

Vyjádřete jediným kombinačním číslem:

\(\displaystyle{20 \choose 6} + \displaystyle{20 \choose 13}\)

Řešení

\(\displaystyle{20 \choose 6} + \displaystyle{20 \choose 13} =\) \(\displaystyle{20 \choose 6} + \displaystyle{20 \choose 7} =\) \(\displaystyle{21 \choose 7}\)

Příklad

Vyjádřete jediným kombinačním číslem:

\(\displaystyle{4 \choose 4} + \displaystyle{5 \choose 4} + \displaystyle{6 \choose 4} + \displaystyle{7 \choose 4} + \displaystyle{8 \choose 4}\)

Řešení

Nejprve si uvědomíme, že platí \(\displaystyle{n \choose n} = 1\), a proto \(\displaystyle{4 \choose 4} = \displaystyle{5 \choose 5}\).

Dále opakovaně použijeme poslední uvedenou vlastnost

\(\displaystyle{n \choose k} + \displaystyle{n \choose k+1} = \displaystyle{n+1 \choose k+1}\)
 
\(\displaystyle{4 \choose 4}\) \(+\) \(\displaystyle{5 \choose 4}\) \(+\) \(\displaystyle{6 \choose 4}\) \(+\) \(\displaystyle{7 \choose 4}\) \(+\) \(\displaystyle{8 \choose 4}\) \(=\)
\(=\) \(\displaystyle{5 \choose 5}\) \(+\) \(\displaystyle{5 \choose 4}\) \(+\) \(\displaystyle{6 \choose 4}\) \(+\) \(\displaystyle{7 \choose 4}\) \(+\) \(\displaystyle{8 \choose 4}\) \(=\)
\(=\) \(\displaystyle{6 \choose 5}\) \(+\) \(\displaystyle{6 \choose 4}\) \(+\) \(\displaystyle{7 \choose 4}\) \(+\) \(\displaystyle{8 \choose 4}\) \(=\)
\(=\) \(\displaystyle{7 \choose 5}\) \(+\) \(\displaystyle{7 \choose 4}\) \(+\) \(\displaystyle{8 \choose 4}\) \(=\)
\(=\) \(\displaystyle{8 \choose 5}\) \(+\) \(\displaystyle{8 \choose 4}\) \(=\)
\(=\) \(\displaystyle{9 \choose 5}\)