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) ?
 A: 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.
A: By way of enrichment here is a proof using generating functions.
Suppose we seek to evaluate
$$\sum_{m=k}^n (k+1)^{n-m} {m\brace k}
= (k+1)^n \sum_{m=k}^n (k+1)^{-m} {m\brace k}.$$
This is
$$(k+1)^n \sum_{m=0}^{n-k} (k+1)^{-m-k} {m+k\brace k}$$
or
$$(k+1)^{n-k} \sum_{m=0}^{n-k} (k+1)^{-m} {m+k\brace k}.$$
What we have here is
$$(k+1)^{n-k} [z^{n-k}] \frac{1}{1-z}
\sum_{m\ge 0} {m+k\brace k} \frac{z^m}{(k+1)^m}.$$
Now recall the OGF of Stirling numbers with fixed $k$
which was evaluated e.g. at this
MSE link:
$$P(z) = \sum_{m\ge 0}{m\brace k} z^m
= \prod_{p=1}^k \frac{z}{1-pz}.$$
This is
$$\sum_{m\ge k}{m\brace k} z^m
= \sum_{m\ge 0}{m+k\brace k} z^{m+k}.$$
It follows that
$$\sum_{m\ge 0}{m+k\brace k} z^{m}
= \prod_{p=1}^k \frac{1}{1-pz}.$$
Substituting this into the sum yields
$$(k+1)^{n-k} [z^{n-k}] \frac{1}{1-z}
\prod_{p=1}^k \frac{1}{1-pz/(k+1)}
\\ = (k+1)^{n-k} [z^{n-k}]
\prod_{p=1}^{k+1} \frac{1}{1-pz/(k+1)}
\\ = (k+1)^{n-k} [z^{n-k}] 
\prod_{p=1}^{k+1} \frac{k+1}{k+1-pz}
\\ = (k+1)^{n+1} [z^{n-k}] 
\prod_{p=1}^{k+1} \frac{1}{k+1-pz}.$$
This is
$$\frac{(k+1)^{n+1}}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n-k+1}}
\prod_{p=1}^{k+1} \frac{1}{k+1-pz} \; dz.$$
Put $z=(k+1) w$ so that $dz = (k+1)\; dw$ to get
$$\frac{(k+1)^{n+1}}{2\pi i}
\int_{|w|=\epsilon} \frac{k+1}{w^{n-k+1}(k+1)^{n-k+1}}
\prod_{p=1}^{k+1} \frac{1}{k+1-p(k+1)w} \; dw$$
which is
$$\frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{k+1}{w^{n-k+1}(k+1)^{-k}}
\prod_{p=1}^{k+1} \frac{1}{k+1-p(k+1)w} \; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^{n-k+1}(k+1)^{-(k+1)}}
\prod_{p=1}^{k+1} \frac{1}{k+1-p(k+1)w} \; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^{n-k+1}}
\prod_{p=1}^{k+1} \frac{1}{1-pw} \; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{w^{k+1}}{w^{n+2}}
\prod_{p=1}^{k+1} \frac{1}{1-pw} \; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^{n+2}}
\prod_{p=1}^{k+1} \frac{w}{1-pw} \; dw.$$
This last integral evaluates to
$${n+1\brace k+1}$$
by inspection.
