Tożsamość liczb Stirlinga II rodzaju

[aolo23]

Uzasadnij że
Liczby Stirlinga II rodzaju spełniają następującą tożsamość
\(\displaystyle{ \left\{ \begin{matrix} n+1\\ m+1\\ \end{matrix} \right\} = \sum_{k=m}^{n} {n \choose k}\left\{ \begin{matrix} k\\ m\\ \end{matrix} \right\}}\)

[janusz47]

Dla dowodu rozważmy zbiór wszystkich \(\displaystyle{ S(n+1, m+1)}\) podziałów zbioru \(\displaystyle{ X=\{ 1,...,n+1\}}\).

Zbiór ten rozpada się na rozłączne klasy odpowiadające różnym podzbiorom zbioru \(\displaystyle{ X}\) będącym blokiem zawierającym element \(\displaystyle{ n+1.}\)

Zauważmy, że dla każdego \(\displaystyle{ b-}\) elementowego podzbioru \(\displaystyle{ B \subseteq X}\) istnieje dokładnie \(\displaystyle{ S(n+1-b, m )}\) podziałów zbioru \(\displaystyle{ X}\) na \(\displaystyle{ m+1}\) bloków zawierających zbiór \(\displaystyle{ B}\) w charakterze bloku.

Istotnie każdy taki podział odpowiada jednoznacznie podziałowi zbioru \(\displaystyle{ X\setminus B}\) na \(\displaystyle{ m}\) bloków.

Zbiór \(\displaystyle{ b -}\) elementowy \(\displaystyle{ B \subseteq X}\) zawierający element \(\displaystyle{ n+1}\) możemy wybrać na \(\displaystyle{ {n \choose b-1}}\) sposobów.

Stąd:

\(\displaystyle{ S(n+1, m+1) = \sum_{b=1}^{n+1- m}{n\choose b-1}S(n+1-b , m) = \\ =\sum_{b=1}^{n+1-m}{n\choose n+1-b}S (n+1-b, m) = \sum_{k=m}^{n}{n\choose k}S(k, m).}\)

c.b.d.o.