Stirling numbers: Combinatorial proof of an identity How to prove the following combinatorially ?
\begin{equation}
{n+1 \brace k+1}=\sum_{m=k}^{n}(k+1)^{n-m}{m \brace k}.
\end{equation}
My question is how are only ( n - m ) elements being considered to be placed on the (k + 1) boxes ? And that too without any combination like n C (n - m) ?

Suppose that you have a distribution of the set $\{1,\ldots,n+1\}$ into $k+1$ identical boxes. Let $m$ be the smallest number such that the set $\{1,\ldots,m\}\cup\{n+1\}$ contains an element of every box. In other words, $m$ is the smallest number such that $\{1,\ldots,m\}$ contains an element of each of the $k$ boxes not containing $n+1$. Clearly $k\le m\le n$. How many distributions share this number $m$?


*

*There are ${m\brace k}$ ways to distribute the numbers $1,\ldots,m$ amongst the $k$ boxes not containing $n+1$.

*The The $n-m$ elements of $\{m+1,\ldots,n\}$ can then be distributed arbitrarily amongst the $k+1$ boxes in $(k+1)^{n-m}$ ways.
Thus, there are a total of $(k+1)^{n-m}{m\brace k}$ distributions of $\{1,\ldots,n+1\}$ into $k+1$ identical boxes that share this value of $m$, and hence
$$\sum_{m=k}^n(k+1)^{n-m}{m\brace k}$$
distributions altogether.
