3.7 Faktoriál a kombinační čísla

Faktoriál kladného přirozeného čísla \(n\) je definován předpisem \begin{equation*} n! := \prod_{k=1}^n k.\end{equation*} Připomeňme, že se dále zvlášť definuje faktoriál nuly, \(0! := 1\). Faktoriál záporných celých čísel není definován.

Faktoriál lze rozšířit na všechna reálná čísla vyjma záporných celých čísel. Tímto rozšířením je speciální funkce \(\Gamma\), která splňuje \(\Gamma(n+1) = n!\) pro \(n\in\N_0\) a navíc platí \(\Gamma(x+1) = x\Gamma(x)\) pro \(x\in\mathbb{R}\smallsetminus\{\ldots,-2,-1,0\}\). S funkcí \(\Gamma\) se čtenář zajisté setká v předmětu Pravděpodobnost a statistika (BI-PST).

Kombinační čísla nacházejí často uplatnění v praktických výpočtech. Pro přirozené \(n\) a celé \(k\) splňující \(0 \leq k \leq n\) definujeme \begin{equation*} \binom{n}{k} := \frac{n!}{(n-k)!k!}.\end{equation*} Ačkoliv tato definice vypadá nepřehledně, skutečný význam kombinačního čísla \(\binom{n}{k}\) je prostý. Toto číslo představuje počet způsobů, jak z \(n\) objektů vybrat \(k\) objektů, nezáleží-li na pořadí a neuvažujeme-li opakovaný výběr již vybraného objektu.

Často se hodí znát všechna kombinační čísla pro pevné \(n\). K jejich výpočtu lze použít Pascalův trojúhelník. Nejprve si všimněme, že platí rovnost

Skutečně, \begin{equation*} \begin{aligned} \binom{n}{k-1} + \binom{n}{k} &= \frac{n!}{(n-k+1)!(k-1)!} + \frac{n!}{(n-k)!k!} = \\ &= \frac{n!}{(n-k)!(k-1)!} \Bigg( \underbrace{\frac{1}{n-k+1} + \frac{1}{k}}_{\frac{n+1}{(n-k+1)k}} \Bigg) = \\ &= \frac{(n+1)!}{(n-k+1)!k!} = \binom{n+1}{k}. \end{aligned}\end{equation*} Představme si, že uspořádáme kombinační čísla do tzv. Pascalova trojúhelníku. Vzorec (3.20) nám pak říká, že součet sousedních kombinačních čísel najdeme o řádek níže. Viz obrázek 3.8.

Řádky Pascalova trojúhelníky indexujeme od nuly, např. tedy v nultém řádku je pouze \(1\), v prvním řádku \(1,1\), ve druhém řádku \(1,2,1\) atd. Tento způsob indexování je konvenčně zvolen tak, aby kombinační čísla \(\binom{n}{k}\) ležela v \(n\). řádku. Snadněji se pak také pamatuje binomická věta (viz rovnici 2.1), koeficienty pro výraz \((a+b)^n\) hledáme v \(n\). řádku (kdybych Pascalův trojúhelník indexovali od jedné, pak by tyto koeficienty byly v \((n-1)\). řádku, což by nebylo hezké).