Kombinatoryczne udowodnienie własności z I liczba Stirlinga

[Kuber19]

Udownodnić, że \(\displaystyle{ \left[ \frac{n+1}{m+1} \right]=n! \sum_{k=0}^{n} \left[ \frac{k}{m} \right]}\) (Tam oczywiscie nie ma kreski ulamkowej, ale nie wiem jak zapisac w Latex). W każdym razie mam to udowodnic poslugując się interpretacją kombinatoryczną, jako że nie wiem co to znaczy, to zacząłem z indukcji matematycznej i doszedłem do następujacego rownania :
\(\displaystyle{ (n+1)\left[ \frac{n+1}{m+1} \right] + \left[ \frac{n+1}{m} \right]=\left[ \frac{n+1}{m+1} \right] +
\frac{1}{n+1} \left[ \frac{n+1}{m} \right]}\) i tu sie zazcyna moj problem, bo ani nie umiem tego skonczyć, ani znaleźć interpretacje kombinatoryczną.

[Gouranga]

\(\displaystyle{ \left[ \begin{array}{c}n+1\\m+1\end{array} \right]=n! \sum_{n}^{k=0} \left[ \begin{array}{c}k\\m\end{array} \right]}\)
o taki zapis chodziło?

[Kuber19]

Tak. Oczywiscie \(\displaystyle{ k}\) w sumie na dole, juz poprawilem

[Mruczek]

Ta tożsamość nie jest prawdziwa. Np. sprawdź wartości dla \(\displaystyle{ n = 4}\), \(\displaystyle{ m = 2}\).
Najprawdopodobniej zabrakło \(\displaystyle{ k!}\) w mianowniku.
Za to prawdziwa jest tożsamość:
\(\displaystyle{ \left[ \begin{array}{c}n+1\\m+1\end{array} \right]=n! \sum_{k = 0}^{n} \frac{1}{k!} \left[ \begin{array}{c}k\\m\end{array} \right]}\)

Dowód kombinatoryczny:    

Przekształćmy prawą stronę:
\(\displaystyle{ n! \sum_{k = 0}^{n} \frac{1}{k!} \left[ \begin{array}{c}k\\m\end{array} \right] =
\sum_{k = 0}^{n} \frac{n!}{k!} \left[ \begin{array}{c}k\\m\end{array} \right] =
\sum_{k = m}^{n} {n \choose n - k} \cdot (n - k)! \left[ \begin{array}{c}k\\m\end{array} \right]}\)
Pokażemy, że to powyżej to \(\displaystyle{ \left[ \begin{array}{c}n+1\\m+1\end{array} \right]}\), czyli liczba permutacji \(\displaystyle{ n + 1}\)-elementowych o \(\displaystyle{ m + 1}\) cyklach.
Załóżmy, że \(\displaystyle{ n - k}\) to liczba elementów które są na cyklu razem z liczbą \(\displaystyle{ n + 1}\). Sumujemy po \(\displaystyle{ k}\), czyli liczbie elementów, które nie są na cyklu razem z liczbą \(\displaystyle{ n + 1}\). Wybieramy \(\displaystyle{ n - k}\) liczb spośród \(\displaystyle{ n}\), które będą na cyklu razem z liczbą \(\displaystyle{ n + 1}\) na \(\displaystyle{ {n \choose n - k}}\) sposobów. Możemy ustawić je na tym cyklu \(\displaystyle{ n - k + 1}\) elementowym na \(\displaystyle{ (n - k)!}\) sposobów. To daje \(\displaystyle{ {n \choose n - k} \cdot (n - k)!}\) różnych cykli \(\displaystyle{ n - k + 1}\) elementowych z liczbą \(\displaystyle{ n + 1}\). Pozostałe \(\displaystyle{ k}\) liczb umieszczamy w \(\displaystyle{ m}\) cyklach na \(\displaystyle{ \left[ \begin{array}{c}k\\m\end{array} \right]}\) sposobów, cnd.

Tutaj masz więcej tego typu tożsamości: