An identity involving Stirling numbers of the second kind and binomial coefficients

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.

-
Why do "we need to prove" it? –  Sasha Apr 24 '13 at 1:38
Could you explain more fully what $S(n,k)$ means? Maybe with an example? Also what is the notation of $[n]$ doing here, rather than simply $n$? Maybe you are referring to the number of partitions of $n$ into $k$ parts, so that e.g. the sum $9=3+3+2+1$ would be counted in $S(9,4)$ since it's a partition of $9$ and there are $4$ numbers added on the right. Is that what it is? Otherwise it seems useless to try the problem. –  coffeemath Apr 24 '13 at 1:46
@coffeemath $[n]$ is commonly used to denote the set $\{1,\ 2,\ \cdots,\ n\}$. I'm interpreting $S(n,k)$ here as the Stirling numbers of the second kind. –  EuYu Apr 24 '13 at 5:21
@vercammen Why would you delete vital information from the question? –  EuYu Apr 24 '13 at 5:36
accidentally did that ,sorry –  John Lennon Apr 24 '13 at 5:46
show 1 more comment

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

-

This sum can also be evaluated with the technique of annihilated coefficient extractors (ACE).

Start with the generating function $$F(w) = \sum_{r\ge 0} \frac{w^r}{r!} \sum_{j=0}^r {n\choose j} \times j! \times (1+x)^{n-j} \times x^j \times {r\brace j}.$$

Recall the bivariate generating function for the Stirling numbers of the second kind which is $$G(z, u) = \exp(u(\exp(z)-1)).$$

Substitute this into the generating function to get $$F(w) = \sum_{r\ge 0} \frac{w^r}{r!} \sum_{j=0}^r {n\choose j} \times j! \times (1+x)^{n-j} \times x^j \times r! [z^r] \frac{(\exp(z)-1)^j}{j!}.$$

Switching summations we obtain $$F(w) = \sum_{j\ge 0} {n\choose j} \times (1+x)^{n-j} \times x^j \times \sum_{r\ge j} w^r [z^r] (\exp(z)-1)^j.$$

The inner sum contains an annihilated coefficient extractor and thus $F(w)$ simplifies to $$F(w) = \sum_{j\ge 0} {n\choose j} \times (1+x)^{n-j} \times x^j \times (\exp(w)-1)^j.$$

Apply the binomial theorem to get $$F(w) = (x(\exp(w)-1) + 1 + x)^n = (1 + x\exp(w))^n.$$ Expand with the binomial theorem to obtain $$F(w) = \sum_{k=0}^n {n\choose k} x^k \exp(kw).$$

Perform coefficient extraction to conclude: $$r! [w^r] F(w) = r! [w^r] \sum_{k=0}^n {n\choose k} x^k \exp(kw) = r! \times \sum_{k=0}^n {n\choose k} x^k \frac{k^r}{r!} = \sum_{k=0}^n {n\choose k} x^k k^r.$$

The ACE technique is also used at this MSE link.

-

If you denote the operator of differentiating and multiplying by $x$ as $D_{x}$

Then we have that

$$(D_{x})^{n}f(x) = \sum_{k=1}^{n} s(n,k) f^{(k)}(x) x^{k}$$

where $s(n,k)$ is the stirling number of the second kind and $f^{(k)}(x)$ is the $k^{th}$ derivative of $f(x)$.

This can easily be proven using the identity $$s(n,k) = s(n-1,k-1) + k \cdot s(n-1,k)$$

Your identity is just $D_x$ applied to $$\frac{(1+x)^n}{n!}$$ $r$ times. Your $S(r,j)$ is same as $s(r,j)$ above.

-