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

1 Úvod 2 Matematika není jen počítání 3 Základní pojmy 3.1 Poznámka k matematické notaci 3.2 Množiny a operace s nimi 3.3 Číselné množiny 3.4 Význačné podmnožiny množiny reálných čísel 3.5 Výroky a logické spojky 3.6 Zkrácené psaní součtů a součinů 3.7 Faktoriál a kombinační čísla 3.8 Významné konstanty 4 Elementární funkce 5 Analytická geometrie 6 Časté problémy 7 Přehled použitého značení Index Literatura

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 Vybrané statistické metody (NI-VSM).

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 jednoduchý. 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

\begin{equation}\label{eqKomb}\tag{3.20} \binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}. \end{equation}

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 v rovnici (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íku 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$-tém řá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$-tém řádku (kdybychom Pascalův trojúhelník indexovali od jedné, pak by tyto koeficienty byly v $(n-1)$-tém řádku, což by nebylo hezké).

Obrázek 3.8: Pascalův trojúhelník.