Combinatorial proof that the Stirling numbers of second kind satisfy $S(m+n+1,m) = \sum_{k=0}^{m} kS(n+k,k)$

Question

Give a combinatoric proof for the identity
$S(m+n+1,m) = \sum_{k=0}^{m} kS(n+k,k)$

LHS gives us a way to partition $m+n+1$ elements into $m$ blocks. How will we interpret $k$?

Answer 1

Note that we can rewrite this as $$ S(n+m+1,m) = \sum_{k=1}^{m}k \, S(n+k,k) = \sum_{s=n+2}^{n+m+1}(s-n-1)\, S(s-1,s-n-1) = \sum_{s=n+2}^{n+m+1} (m - (n+m+1-s)) \, S(s-1,m-(n+m+1-s)), $$ by substituting $s = n+k+1.$

Let $P$ be a partition of the set $\{1, \dots, n+m+1\}$ into $m$ parts. Let $s$ be the largest element of $\{1, \dots, n+m+1\}$ that is not in a singleton (a singleton is a part that contains only one element). This means that the $n+m+1-s$ elements $s+1, s+2, \dots, n+m+1$ are all in singletons. The partition has $m-(n+m+1-s)$ other parts. This induces a partition of the elements in $\{1,\dots,s-1\}$ into $m-(n+m+1-s)$ parts by removing the element $s$ from its part in $P$ and removing the singletons with elements larger than $s$. Note that there are $S(s-1,m-(n+m+1-s))$ many such partitions. Now there are $m-(n+m+1-s)$ ways to choose the part to which the element $s$ belongs. ($s$ is not in a singleton.) Summing over all possible choices for $s$ gives the result.