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?

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.
