permutacje i silnia

[epicka_nemesis]

Uzasadnij wzór:
\(\displaystyle{ m!=\sum_{i=1}^{m}i{\cdot}c_{m}(i)}\)
gdzie \(\displaystyle{ c_{m}(i)}\) oznacza liczbę permutacji zbioru m elementowego z i punktami stałymi.

[Premislav]

Pewnie istnieje jakieś natychmiastowe rozwiązanie z użyciem pięknej interpretacji kombinatorycznej, ale pomyślałem, że można po prostu bezczelnie policzyć \(\displaystyle{ c_{m}(i)}\):
\(\displaystyle{ c_{m}(i)={m \choose i}N(m-i)}\), gdzie N(m-i) to liczba nieporządków w zbiorze o \(\displaystyle{ m-i}\) elementach, bo na \(\displaystyle{ {m \choose i}}\) sposobów wybieramy \(\displaystyle{ i}\) punktów stałych ze zb. \(\displaystyle{ m}\)-elementowego, a pozostałe \(\displaystyle{ m-i}\) permutujemy tak, aby żaden z nich nie "pozostał na starym miejscu". Zatem mamy
\(\displaystyle{ \sum_{i=1}^{m}ic_{m}(i)= \sum_{i=1}^{m}i{m \choose i} N(m-i)}\)
Teraz skorzystajmy z tożsamości \(\displaystyle{ k{n \choose k}=n{n-1 \choose k-1}}\):
\(\displaystyle{ \sum_{i=1}^{m}i{m \choose i} N(m-i)= \sum_{i=1}^{m}m{m-1 \choose i-1}N(m-i)}\)
Następnie przesuńmy indeksy:
\(\displaystyle{ \sum_{i=1}^{m}m{m-1 \choose i-1}N(m-i)= \\=\sum_{i=0}^{m-1}m{m-1 \choose i}N(m-1-i)=m \sum_{i=0}^{m-1}{m-1 \choose i}N(m-1-i)=m\cdot (m-1)!}\)
I gotowe.

Krótkie zdanie czy dwa wyjaśnienia: \(\displaystyle{ \sum_{i=0}^{m-1}{m-1 \choose i}N(m-1-i)= \sum_{i=0}^{m-1}c_{m-1}(i)}\) (wypr. jak wyżej). A zatem sumujemy od \(\displaystyle{ i=0}\) do \(\displaystyle{ i=m-1}\)
permutacje zbioru o \(\displaystyle{ m-1}\) elementach, mające dokładnie i punktów stałych - no czyli łącznie otrzymujemy wszystkie permutacje zbioru \(\displaystyle{ m-1}\)-elementowego.
Wybacz brzydotę, jak wspominałem pewnie odpowiednia interpretacja rozwala to w jednej linijce, ale że nie umiem myśleć, to muszę się chwytać przekształceń algebraicznych jak tonący brzytwy.

[kropka+]

Można to udowodnić indukcyjnie.

[epicka_nemesis]

Można to udowodnić indukcyjnie.

Czyli?