Kombinatorika

Teda $n!=1. 2 ...(n-1).n$ je prirodzené číslo, ktoré skrátene nazývame $n$- faktoriál. Symbol $0!$ definitoricky bude predstavovať číslo rovné $1$.
V nasledujúcom texte budeme pre kombinačné číslo používať označenie $\small   C (n,r) = \binom {n} {r}$

Dôkaz.

1. Pre $r=0$ pravdivosť tvrdenia je zrejmá.
2. Predpokladajme, že platí $1 \leq r \leq n$. Budeme dokazovať indukciou vzhľadom na číslo $n$.
• Overenie pravdivosti tvrdenia v prípade $n=1$ prenechávame na čitateľa.
• Predpokladajme (indukčný predpoklad), že tvrdenie platí pre $k \leq n-1$.
  $\small   \binom {n-1} {r-1} =\frac{(n-1)!}{(n-r)! (r-1)!}$
  $\small  \binom {n-1} {r} =\frac{(n-1)!}{(n-1-r)! (r-1)!}$
  Dokážeme, že platí aj pre $n$.
3. Na základe predchádzajúceho dôsledku platí rovnosť:
       $\small   \binom {n} {r} =\binom {n-1} {r-1}+\binom {n-1} {r}$
4. na základe indukčného predpokladu môžeme rovnosť ďalej upraviť: applet

Tu                
Všimnite si zaujímavý fakt: $\frac{n!}{(n-r)!\; r!}$ je celé číslo pre ľubovoľné $n$ a $r$, $1 \leq r \leq n$.

$<span class="nolink">\( .$\)