Santa Claus — modified 2021-11-07 22:36 (423 days ago) — edit — reply
Početně:
Indukcí:
pro $n = r$
$\binom{r}{r} = 1 = \binom{r+1}{r+1}$
Pokud platí pro $n$, dokazme pro $n+1$
$\sum^{n+1}_{k=r} \binom{k}{r} = \sum^{n}_{k=r} \binom{k}{r} + \binom{n+1}{r} =
\binom{n+1}{r+1} + \binom{n+1}{r}$
Toto můžeme sečíst
$\sum^{n+1}_{k=r} \binom{k}{r}=\binom{n+2}{r+1}$
Takže tvrzení platí.
Kombinatoricky:
Rozložme výběr r+1 z n+1 prvků podle toho, kdo bude první vybraný. Pokud prvního zařadíme do výběru, pak vybíráme zbylých r z n, pokud prvního nevybereme a druhého ano, pak nám bude zbývat vybrat r z n-1. Takhle pokračujeme až dokud nevybereme prvních n-r prvků a pak už musíme vybrat těch zbylých r.