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
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
Related: math.stackexchange.com/questions/355262/… –  Aryabhata Apr 24 '13 at 9:05

4 Answers 4

up vote 4 down vote accepted

I claim first that


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

Here is a combinatorial argument. Let us use the same notation for a natural number $x$ and for a set with $x$ elements.

On the left, you have cardinality of the set of data $(k\subseteq n, r\to k\to x)$ (meaning a $k$-element subset of $n$, a map from $r$ to this subset, and a map from this subset to $x$).

On the right, you have cardinality of the set of data $(j\subseteq n, r\twoheadrightarrow j, j\to x,(n-j)\to(1+x))$, (meaning a $j$-element subset of $n$, a map from $r$ onto this subset, a map from this subset to $x$, and another map from the complement of this subset to $1+x$ (this is clear - maybe just additionally noting that the number of onto maps from $r$ to $j$ equals $j!S(r,j)$)).

Now it is almost obvious how to establish a one-to-one correspondence between these kinds of data. Given $(k\subseteq n, r\to k\to x)$, let $j$ be the image of $r\to k$, let $j\to x$ be the restriction of $k\to x$ to $j\subseteq k$, and let $(n-j)\to(1+x)$ be given by sending $k-j$ to $x$ according to the given $k\to x$, and the remaining $n-k$ to $1\in(1+x)$. Conversely given data of the second kind, let $k$ be the (disjoint) union of $j$ and the inverse image of $x$ under $(n-j)\to(1+x)$, let $r\to k$ be the composite $r\twoheadrightarrow j\hookrightarrow k$, and let $k\to x$ be as $j\to x$ on $j$ and as $(n-j)\to(1+x)$ on the rest of $k$.

share|improve this answer

Your Answer


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.