Loading [MathJax]/extensions/TeX/boldsymbol.js

\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}