Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
@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

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.