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}},$

${\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{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}}$

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

$\sum _{i=1}^{n}{i}={{N+1} \choose {2}}={{N+1} \choose {n-1}}={\frac {n}{2}}(n+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 používán hlavně v 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

• Obrázky, zvuky či videa k tématu kombinační číslo na Wikimedia Commons
• Kombinační číslo na encyklopedii MathWorld (anglicky)
• Kalkulátor kombinačního čísla

Autoritní data	GND: 4145586-1

Portály: Matematika