Kombinační číslo

Kombinační číslo je matematická funkce, která udává počet kombinací, tzn. způsobů, jak vybrat $k$-prvkovou podmnožinu z $n$-prvkové množiny ($k\,$ a $n\,$ jsou čísla přirozená). Kombinační číslo se značí ve tvaru ${n \choose k}$ (čte se „n nad k“), někdy se používá také značení $_n C_k\,$, $C(n, k)\,$ či $C_n^k$. Při použití faktoriálu je kombinační číslo obecně rovno

${n \choose k} = \left\{ \begin{matrix} \frac{n!}{k!(n-k)!}\,&&\mbox{pro }n \geq k \geq 0; \\ 0\,&&\mbox{jinak,}\,\qquad\qquad \end{matrix} \right.$

Platí rovnost

$1 = {0 \choose 0} = {n \choose 0} = {n \choose n}.$

Kombinační číslo se používá hlavně v kombinatorice, velice důležité je využití v binomické větě (přičemž je zde označováno jako binomický koeficient) či Leibnizově pravidle.

Základní vlastnosti

Pro přirozená čísla n a k, kde $0 \leqq k \leqq n$ a $m \in \mathbb{N}$ platí

${n \choose k} = {n \choose {n-k}},$

${{n} \choose {1}} = n,$

${{n} \choose {0}} = {{n} \choose {n}} = 1,$

${n \choose {k+1}} = {n \choose k}\frac{n-k}{k+1},$

${{n+1} \choose {k}} = {n \choose k}+{n \choose {k-1}},$

${{n-1} \choose {k-1}} + {{n-1} \choose {k}} = {n \choose {k}},$

$\sum_{i=k}^n {i \choose {k}} = {n+1 \choose {k+1}},$

$\sum_{i=0}^n {{k+i} \choose {i}} = {k+n+1 \choose n},$

$\sum_{i=0}^n {n \choose {i}} = 2^n,$

$\sum_{i=0}^n (-1)^i{n \choose {i}} = 0,$

$\sum_{i=0}^n {n \choose {i}}^2 = {2n \choose {n}}={{n+m+1} \choose {k+1}}-{{n+1} \choose {k+1}}$

$\sum_{i=0}^m {{n+i} \choose {n}}={{n+m+1} \choose {n+1}}$

$\sum_{i=0}^m{{n+i} \choose k}={{n+m+1} \choose {k+1}}-{{n+1} \choose {k+1}}$

Zobecnění kombinačních čísel

Pokud definujeme kombinační číslo takto

${z \choose k} = \frac{z (z-1)(z-2)\cdots (z-k+1)}{k!}$,

kde $k$ je nezáporné celé číslo, pak je zřejmé, že pravá strana má smysl, i když číslo $z$ není celé nezáporné. Na číslo $z$ dokonce nemusíme klást žádné podmínky, může se jednat dokonce o číslo komplexní. Vztah je tedy přirozeným zobecněním kombinačních čísel a je požíván hlavně ve zobecněné binomické větě.

Další možnou definici nám umožňuje nahrazení faktoriálu gama funkcí

${z \choose k} = \frac{\Gamma(z+1)}{\Gamma(z-k+1)\Gamma(k+1)}$

kde $z$ i $k$ mohou být komplexní čísla - pak ovšem nebudou platit popsané vlastnosti kombinačních čísel pro všechny hodnoty.

Odkazy

Literatura

• MATOUŠEK, Jiří; NEŠETŘIL, Jaroslav. Kapitoly z diskrétní matematiky. 3., upravené a doplněné vyd. Praha : Karolinum, 2007. ISBN 978-80-246-1411-3. Kapitola 3. Kombinatorické počítání, s. 76–82.  
• BARTSCH, Hans-Jochen. Matematické vzorce. 4., upravené vyd. Praha : Academia, 2006. ISBN 80-200-1448-9. Kapitola 1.7.1. Binomické koeficienty, binomická věta, s. 156–160.  

Související články

• Pascalův trojúhelník
• Binomická věta
• Kombinatorika

Externí odkazy

• Kombinační číslo na encyklopedii MathWorld (anglicky)
• Kalkulátor kombinačního čísla