Kombinatorika

Predpokladáme, že študentom sú známe vzorce pre mocniny dvojčlena $(a+b)^n$ ak $n=2$ resp. pre $n=3$. Pre umocňovanie s vyšším exponentom odvodíme vzorce pomocou tzv. binomickej vety, ktorú teraz dokážeme.

Binomická veta
Nech $x,y$ sú ľubovoľné reálne čísla a nech $n$ je prirodzené číslo, potom
$(a+b)^n = {n \choose 0}a^n b^0 + {n \choose 1}a^{n-1}b^1 + {n \choose 2}a^{n-2}b^2 + \cdots + {n \choose n-1}a^1 b^{n-1} + {n \choose n}a^0 b^n,$ 

Pre $n=2$ resp. $n=3$ dostaneme známe vzorce:
$(a+b)^2= \binom {2} {0} a^2 b^0 +\binom {2} {1} a^1 b^1+\binom {2} {2} a^0 b^2=a^2+2ab+b^2$
$(a+b)^3= \binom {3} {0} a^3 b^0 +\binom {3} {1} a^2 b^1+\binom {3} {2} a^1 b^2+\binom {3} {3} a^0 b^3 = a^3+3a^2b+3ab^2+ b^3$

 Dôkaz vety.
Pri dôkaze binomickej vety vychádzame z toho, že v súčine
$(a+b)(a+b) \cdot \cdot \cdot (a+b)$
člen
$a^{n-k} b^k$
dostaneme tak, že z dvojčlenov $(a+b)$ vyberieme $(n-k)$-krát reálne číslo $a$ a potom $k$-krát reálne číslo $b$. To je možné práve
$C(n,n-k)=C(n,k)$
spôsobmi, čím je dôkaz ukončený. Dôkaz binomickej vety môžeme urobiť aj pomocou úplnej matematickej indukcie.

Poznámky.

1. V binomickej vete sa objavujú kombinačné čísla. Preto ich niekedy nazývame binomické koeficienty.
2. Ak v binomickej vete položíme $a=1,b=1$ dostaneme identitu
   $\sum_{k=0}^{n}{ \binom {n} {k} =2^n}$.
3. Počet všetkých kombinácií (podmnožín) množiny $M_n$ sa rovná $2^n$.
4. Inú identitu dostaneme, ak v binomickej vete kladieme $a = -1,b = 1$
   $\sum_{k=0}^{n}{ (-1)^k\binom {n} {k} =0}$.

Príklad. Využitím binomickej vety vypočítajte $1,2^4$.