[kombinatoryka] uzasadnić wzór
: 23 kwie 2011, o 12:38
Uzasadnić wzór:
\(\displaystyle{ {n-1 \choose k-1} = \sum_{i=1}^{n-1} {n-i-1 \choose k-2}}\)
\(\displaystyle{ {n-1 \choose k-1} = \sum_{i=1}^{n-1} {n-i-1 \choose k-2}}\)
Spróbuj metodą bijektywną.
Po lewej stronie masz ilość (k-1)-elementowych podzbiorów (n-1) elementowego zbioru, a po prawej - sumę mnogościową (k-1)-elementowych podzbiorów zbiorów (n-i-1)-elementowych (suma mnogościowa przebiega po i)