A combinatorial identity involving Stirling numbers of the second kind Answering a recent question I came across the following interesting identity:
$$
\sum_{k=0}^m\binom mk{n+k+1 \brace k+1}k!=\sum_{k=0}^m\binom mk (-k)^{m-k}(k+1)^{n+k}.
$$
Is there a simple way to prove it?
 A: Consider the following problem. You want to count the number of functions $f$ form $[n+m]$ to $[m+1]$ such that for $y\in [m]\subseteq [m+1],$ if $f^{-1}(y)= \emptyset,$ then $f(y)=m+1$ (such elements $y$ will be called special).
In the LHS you have this counted in the following way. Either you will have $m+1$ in the image of the non-special elements or not. In both cases, select $k$ special elements $y\in [m]$ which can be done in $\binom{m}{k}$ ways, and then make a surjective function of the other elements in ${n+m-k\brace m-k}(m-k)!$ or ${n+m-k\brace m-k+1}(m-k+1)!$ ways (depending on $m+1$ being or being not in the image). You will get
$$LHS = \underbrace{\sum _{k=0}^m\binom{m}{k}{n+m-k\brace m-k}(m-k)!}_{m+1\text{ not in the image}}+\underbrace{\sum _{k=0}^m\binom{m}{k}{n+m-k\brace m-k+1}(m-k+1)!}_{m+1\text{ in the image}}.$$
Which, using the recursion of Stirling numbers, can be seen to be equal to
$$LHS =\sum _{k=0}^m\binom{m}{k}\left ({n+k\brace k}k!+{n+k\brace k+1}(k+1)!\right )=\sum _{k=0}^m\binom{m}{k}k!{n+k+1\brace k+1}.$$

Meanwhile, in the alternative universe of the RHS, you can be think of it as
$$RHS = \sum _{k=0}^m\binom{m}{k}(-1)^{m-k}k^{m-k}(k+1)^{n+k}=\sum _{k=0}^m\binom{m}{k}(-1)^{k}(m-k)^{k}(m-k+1)^{n+m-k},$$
if you put apart the first term looks like
$$RHS = (m+1)^{n+m}-\sum _{k=1}^m\binom{m}{k}(-1)^{k-1}(m-k)^{k}(m-k+1)^{n+m-k},$$
you can think of this as functions from $[n+m]$ to $[m+1]$ with some particular property. The property being the same as for the LHS. Here, you will then construct sets $$A_i = \{f:[n+m]\rightarrow [m+1]:i\text{ is not in the image and }f(i)\neq m+1\}.$$ So, by the PIE principle, you can think of the RHS as
$$\left |[m+1]^{[n+m]}\setminus \bigcup _{i=1}^mA_i\right |.$$
A: We seek to prove the following identity:
$$\sum_{k=0}^m {m\choose k} {n+k+1\brace k+1} k!
= \sum_{k=0}^m {m\choose k} (-k)^{m-k} (k+1)^{n+k}.$$
For the RHS we introduce the polynomial
$$\sum_{k=0}^m {m\choose k} (-k)^{m-k} (x+k)^{n+k}.$$
and extract the coefficient on $[x^q]$ where $0\le q\le n+m$
to get
$$\sum_{k=0}^m {m\choose k} (-1)^{m-k} k^{m-k}
{n+k\choose q} k^{n+k-q}
\\ = \sum_{k=0}^m {m\choose k} (-1)^{m-k}
{n+k\choose q} k^{n+m-q}
\\ = (n+m-q)! [z^{n+m-q}]
\sum_{k=0}^m {m\choose k} (-1)^{m-k}
{n+k\choose q} \exp(kz)
\\ = (n+m-q)! [z^{n+m-q}] [w^q] (1+w)^n
\sum_{k=0}^m {m\choose k} (-1)^{m-k}
(1+w)^k \exp(kz).$$
Working with the inner extractor,
$$[w^q] (1+w)^n ((1+w)\exp(z)-1)^m
\\ = [w^q] (1+w)^n ((1+w)(\exp(z)-1)+w)^m.$$
Expanding the power,
$$(n+m-q)! [z^{n+m-q}] [w^q] (1+w)^n
\sum_{k=0}^m {m\choose k} (1+w)^k
(\exp(z)-1)^k w^{m-k}.$$
This is (here the second binomial coefficient is zero by construction
if $q\lt m-k$)
$$\sum_{k=0}^m {m\choose k} {n+k\choose k+q-m}
k! {n+m-q\brace k}.$$
We require the value at $x=1$ which means we must sum over all $q$ from
the range. We get for the component that is dependent on $q$:
$$\sum_{q=0}^{n+m} {n+k\choose n+m-q}
(n+m-q)! [z^{n+m-q}] \frac{1}{k!} (\exp(z)-1)^k
\\ = \sum_{q=0}^{n+m} {n+k\choose q}
q! [z^q] \frac{1}{k!} (\exp(z)-1)^k.$$
Here we may lower to $n+k$ due to the binomial coefficient:
$$\sum_{q=0}^{n+k} {n+k\choose q}
q! [z^q] \frac{1}{k!} (\exp(z)-1)^k.$$
We have by convolution of EGFs that this is
$$(n+k)! [z^{n+k}] \exp(z) \frac{1}{k!} (\exp(z)-1)^k
\\ = (n+k+1)! [z^{n+k+1}] \frac{1}{(k+1)!} (\exp(z)-1)^{k+1}
= {n+k+1\brace k+1}$$
as required. This concludes the argument.
