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í čísla zapisujeme ${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}$ . Hodnotu kombinačních čísel lze vyjádřit pomocí faktoriálu:

{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í čísla se používají 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), v Leibnizově pravidle nebo při výpočtu pravděpodobnosti v binomickém rozdělení.

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.