Kombinační číslo

Kombinační číslo je matematická funkce, která udává počet kombinací, tzn. způsobů, jak vybrat ${\displaystyle k}$-prvkovou podmnožinu (bez ohledu na pořadí jejích prvků) z ${\displaystyle n}$-prvkové množiny (${\displaystyle k\,}$ a ${\displaystyle n\,}$ jsou čísla přirozená). Kombinační čísla zapisujeme ${\displaystyle {n \choose k}}$ (čte se „n nad k“), někdy se používá také značení ${\displaystyle _{n}C_{k}\,}$, ${\displaystyle C(n,k)\,}$ či ${\displaystyle C_{n}^{k}}$. Hodnotu kombinačních čísel lze vyjádřit pomocí faktoriálu:

${\displaystyle {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.}$

Binomické koeficienty lze uspořádat do tvaru Pascalova trojúhelníka, ve kterém je každá hodnota součtem dvou hodnot ležících nad ní. Pokud počítáme od nuly, tak na ${\displaystyle n}$-tém řádku odshora a ${\displaystyle k}$-té pozici na daném řádku se nachází ${\displaystyle {n \choose k}}$.

Znázornění binomické expanze do čtvrté mocniny

Platí rovnost

${\displaystyle 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 ${\displaystyle 0\leqq k\leqq n}$ a ${\displaystyle m\in \mathbb {N} }$, platí:^[1]

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

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

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

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

${\displaystyle {\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}}$

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

${\displaystyle {{n+1} \choose {k+1}}={n \choose k}+{n \choose {k+1}}}$

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

${\displaystyle \sum _{i=k}^{n}{i \choose {k}}={n+1 \choose {k+1}}}$

${\displaystyle \sum _{i=0}^{n}{{k+i} \choose {i}}={k+n+1 \choose n}}$

${\displaystyle \sum _{i=0}^{n}{n \choose {i}}=2^{n}}$

${\displaystyle \sum _{i=0}^{n}(-1)^{i}{n \choose {i}}=0}$

${\displaystyle \sum _{i=0}^{n}{n \choose {i}}^{2}={2n \choose {n}}}$

${\displaystyle \sum _{i=0}^{m}{{n+i} \choose {n}}={{n+m+1} \choose {n+1}}}$

${\displaystyle \sum _{i=0}^{m}{{n+i} \choose k}={{n+m+1} \choose {k+1}}-{{n+1} \choose {k+1}}}$

${\displaystyle \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

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

kde ${\displaystyle k}$ je nezáporné celé číslo, pak je zřejmé, že pravá strana má smysl, i když číslo ${\displaystyle z}$ není celé nezáporné. Na číslo ${\displaystyle 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í

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

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