Need to prove:
$$\sum\limits_{k=0}^{n} \binom nk k^r x^k = \sum\limits_{j=0}^{r} \binom nj j! (1+x)^{n-j} x^j S(r,j)$$
where $S (n, k)$ denotes a Stirling number of second kind, the number of partitions of a set with $n$ elements into $k$ blocks.
Combinatorics – Identity Involving Stirling Numbers and Binomial Coefficients
binomial-coefficientscombinatoricsstirling-numberssummation
Best Answer
I claim first that
$$\binom{n}kk^r=\sum_{i=\max\{0,k-r\}}^k\binom{n}{i,k-i,n-k}{r\brace{k-i}}(k-i)!\;.\tag{1}$$
The lefthand side of $(1)$ clearly counts the ways to choose $K\subseteq[n]$ such that $|K|=k$ and then choose a function from $[r]$ to $K$. The $i$ term on the righthand side of $(1)$ counts the ways to choose a $k$-element subset $K$ of $[n]$, choose an $i$-element subset $I$ of $K$, and then choose a function from $[r]$ onto $K\setminus I$. Clearly this is possible if and only if $\max\{0,k-r\}\le i\le k$, so the two sides of $(1)$ count the same thing.
Now just rearrange the righthand side of the desired identity, expanding $(1+x)^{n-j}$ by the binomial theorem, making a change of index ($k=i+j$), and reversing the order of summation:
$$\begin{align*} \sum_{j=0}^r\binom{n}j{r\brace j}j!(1+x)^{n-j}x^j&=\sum_{j=0}^r\binom{n}j{r\brace j}j!x^j\sum_{i=0}^{n-j}\binom{n-j}ix^i\\\\ &=\sum_{i=0}^n\sum_{j=0}^{\min\{r,n-i\}}\binom{n}j\binom{n-j}i{r\brace j}j!x^{i+j}\\\\ &=\sum_{i=0}^n\sum_{k=i}^{\min\{i+r,n\}}\binom{n}{k-i}\binom{n-k+i}i{r\brace{k-i}}(k-i)!x^k\\\\ &=\sum_{k=0}^n\sum_{i=\max\{0,k-r\}}^k\binom{n}{i,k-i,n-k}{r\brace{k-i}}(k-i)!x^k\;. \end{align*}$$
Finally, apply $(1)$.