Kombinační čísla
Kombinační číslo
Kombinační číslo je symbol, který označuje počet k-členných kombinací z n prvků.
Definice
\displaystyle{n \choose 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 |
Vlastnosti kombinačních čísel
Věta
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í.
Anna,
Bára,
Cyril,
David,
Eva,
Filip
Přidat rozdělení do tabulky /
Smazat změny
Anna | Bára | Cyril | David | Eva | Filip |
---|
Věta
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} |