Rovnosť $\frac1k \binom km=\frac1m \binom{k-1}{m-1}$

[Martin Sleziak]

V úlohe 7b z 06cvicenie_binom.pdf sa spomína, že pri výpočte uvedenej sumy by nám mohla pomôcť takáto rovnosť
$$\frac1k \binom km=\frac1m \binom{k-1}{m-1}.$$

Hint: Jednoducho si skúste napísať vzorec pre binomický koeficient pomocou vzorca a snažte sa vykrátiť, rozšíriť, upraviť.

Spoiler:

$$\frac1k \binom km = \frac1k \cdot\frac{k(k-1)\cdots(k-m+1)}{m\cdot(m-1)\cdots1} = \frac{(k-1)\cdots(k-m+1)}{m\cdot(m-1)\cdots1} \overset{(*)}= \frac1m\cdot\frac{k(k-1)\cdots(k-m+1)}{(m-1)\cdot(m-2)\cdots1} = \frac1m \binom{k-1}{m-1}.$$

Aj ak by sme nemali zadané, čo chceme dostať, tak sa na rovnosť označenú $(*)$ dá vcelku ľahko prísť. Ak chcem uvedený výraz upraviť tak, aby to bol binomický koeficient a v čitateli máme $(m-1)$ členov a dole $m$, tak musíme jeden dať bokom, aby sme dostali rovnaký počet.

To isté prepísané inak
$$\frac1k \binom km = \frac1k \cdot \frac{k!}{m!(k-m)!} = \frac{(k-1)!}{m!(k-m)!} = \frac1m \cdot \frac{(k-1)!}{(m-1)!(k-m)!} = \frac1m\binom{k-1}{m-1}$$

Táto rovnosť sa ďalej použije pri výpočte sumy. Opäť zatiaľ pridám linku - a ak sa ozvete, že treba niečo napísať aj k výpočtu tej sumy, tak to sem skúsim dopísať.
Expressing sum using simple formula (without summation)

[Martin Sleziak]

S rovnosťou $\frac1k \binom km=\frac1m \binom{k-1}{m-1}$, ktorú máme dokázať je ekvivalentná rovnosť
$$m\binom km=k\binom{k-1}{m-1}.$$
Takáto podoba je azda vhodnejšia, ak chceme použiť kombinatorický dôkaz.
(A môžno si spomeniete, že presne takúto vec sme použili pri sume z úlohy 2 v 06cvicenie_binom.pdf.)

Aj keď to bolo na cviku, skúsim zopakovať aj tu.
Chceme zrátať počet nejakých objektov dvoma spôsobmi tak, aby nám vyšla suma na ľavej resp. pravej strane.
Môžete sa skúsiť zamyslieť, alebo pozrieť na návod.

Spoiler:

Máme $m$-prvkovú množinu $A$ skúste rátať počet dvojíc $(x,B)$ takých, že $x\in B\subseteq A$ a $|B|=k$.

To isté, povedané inak. Spomedzi $m$ ľudí chceme vybrať $k$-členný tím. Navyše spomedzi členov tímu chceme vybrať jedného lídra. Koľko existuje možností výberu?