2. prednáška (29.2):
Hokejkovú identitu, ktorú sme spomenuli na konci minulej prednášky, sme dokázali na cvičeniach.
Permutácie s opakovaním. Počet permutácie pre $n_1,n_2,\dots,n_k$ rôznych typov prvkov a $n=n_1+n_2+\dots+n_k$ je
$$\binom n{n_1,n_2,\dots,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!}.$$
Tomuto výrazu sa zvykne hovoriť aj
multinomický koeficient..
Kombinácie s opakovaním a celočíselné riešenia. Počet kombinácii s opakovaním $k$-tej triedy z $n$ prvkov je rovný $$\binom{n+k-1}{k-1}=\binom{n+k-1}n.$$
Zdôvodnili sme ho pomocou
stars and bars. (Povedali sme si, že pomerne priamočiaro by sa dal dokázať aj indukciou - ale každopádne túto metódu je užitočné poznať.)
Ten istý vzťah nám dá počet celočíselných riešení rovnice $x_1+\dots+x_k=n$ takých, že $x_i\ge0$.
Binomické koeficienty. Pripomenuli sme definíciu binomického koeficientu a niektoré základné vlastnosti (symetria, Pascalova identita.)
Binomická veta. Sfomulovali sme
binomickú vetu v dvoch podobách:
\begin{gather*}
(1+t)^n=\sum_{k=0}^n \binom nk t^k\\
(x+y)^n=\sum_{k=0}^n \binom nk x^ky^{n-k}
\end{gather*}
Povedali sme si, ako sa dá dokázať - aj keď pri dôkaze indukciou som nerobil všetky detaily. (Spomenul som otázku, či platí binomická veta pre polia, okruhy, či sa dá aplikovať na matice - môžeme sa k tejto otázke niekedy vrátiť.)
Keď sme vhodne dosadili do binomickej vety, tak sme dostali, že pre $n\ge1$ platí
$$\sum_{k=0}^n (-1)^k \binom nk=0,$$
t.j. vlastne súčet binomických koeficientov v riadku Pascalovho trojuholníka so striedavými znamienkami. Ako dôsledok dostávame, že máme rovnako veľa podmnožín s párnym a s nepárnym počtom prvkov.
Potom sme ešte binomickú vetu zderivovali a zintegrovali, dostali sme takto identity: $\sum\limits_{k=0}^n k\binom nk = n2^{n-1}$ a $\sum\limits_{k=0}^n \frac1{k+1}\binom nk = \frac{2^{n+1}-1}{n+1}$.
Sľúbil som, že aspoň k niektorým identitám, ktoré sme dostali ako dôsledky binomickej vety, sa ešte vrátime aj na cvičeniach - pozrieme sa na možnosť iného dôkazu (indukciou, kombinatoricky, pomocou iných identít).