Rovnosť $\binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}$

[Martin Sleziak]

K tejto identite:
$$\binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}$$
(Robili sme ju i na cviku - určite aspoň s jednou skupinou.)

Riešenie 1: Prepíšte binomické koeficienty podľa vzorca, ktorý poznáte, a skúste nejaké veci pokrátiť alebo poupravovať.

Riešenie 2 (Kombinatorický prístup): Máme nejakú $n$-prvkovú množinu $|A|=n$. Skúste počítať počet dvojíc podmnožín množiny $A$ takých, že $B\subseteq C\subseteq A$ a $|B|=k$, $|C|=m$. Nejako si skúste rozmyslieť, že pravá i ľavá strana vyjadruje tento počet. Inak povedané, rátate počet prvkov tejto množiny:
$$\{(B,C); B\subseteq C\subseteq A, |B|=m, |C|=k\}.$$

Nejaké linky, ktoré som vedel narýchlo nájsť:
* Proving an identity with a combinatorial proof
* Prove $\binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}$ by counting in two ways

Táto rovnosť sa potom využila vo výpočte nejakej sumy. Ak bude treba, môžem sem napísať niečo aj k tej sume, zatiaľ dám aspoň nejakú linku.
Prove by induction $\sum\limits_{k=m}^{\ n}{n\choose k}{k\choose m}={n\choose m}2^{n-m}$

[Martin Sleziak]

Poznámky k vašim riešeniam z písomky

Ak máte upravovať nejaké výrazy s písmenkami, oplatí sa zamyslieť nad tým, či dávajú zmysel po dosadení konkrétnych čísel.
Napríklad výraz $\binom nm \binom mk$ je očividne celé číslo, bez ohľadu na to, aké sú hodnoty $n$, $m$ a $k$.
Ak sa vám ho podarilo doupravovať na tvar $\frac1{(n-m)m!}\cdot\frac1{(m-k)k!}$ (ktorý očividne pre väčšinu hodnôt nemá celočíselnú hodnotu), tak zrejme niekde nie je niečo v poriadku a treba hľadať chybu.