A combinatorial identity involving Stirling numbers of the second kind

Question

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?

Answer 1

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 |.$$