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.

It's very easy to prove that:

$$\sum_k \left\{k\atop n\right\}z^k=\frac{z^n}{(1-z)(1-2z)...(1-nz)}$$

But this generating function looks very pretty, so my question is: does this identity have some simple combinatorial interpretation?

share|improve this question
add comment

2 Answers

Yes, this equation has a combinatorial interpretation.

The number $\left\{k\atop n\right\}$ counts the number of partitions of the linearly ordered set $\mathbf k=\{1, \dots, k\}$ into $n$ nonempty subsets. Let us see how one can think of such a partition. Below, you can see a partition of $\mathbf{15}$ into $4$ nonempty subsets (the linear order goes from left to right).

enter image description here

The data of this partition is equivalent to the following data:

enter image description here

Here, a vertical line was inserted just before a new color is encountered when going from left to right. The colors were ordered by their order of occurence:

$$\text{Red}<\text{Blue}<\text{Green}<\text{Pink}$$

and were assigned the numbers $0,1,2,3$ respectively. Now, remark that the data of the above decomposition is also equivalent to the data of the diagram

enter image description here

because the obscured numbers are just $0,1,2,3$ in order of occurence. The initial partition can be completely reconstructed from this last diagram. I'll leave it up to you to check that this decomposition yields the claimed identity of power series.

share|improve this answer
1  
Very nice. Every time a new color appears it is followed by a sequence, possibly empty, of repetitions of the $j$ colors we have seen so far, giving the generating function $1/(1-jz)$. The numerator accounts for the black nodes. –  Marko Riedel Nov 18 '13 at 1:49
    
@MarkoRiedel That is precisely it! :) –  Bruno Joyal Nov 18 '13 at 1:54
    
These are sometimes called "rhyming schemes": en.wikipedia.org/wiki/… –  Byron Schmuland Nov 18 '13 at 2:06
add comment

For the sake of completeness we give an algebraic proof of this identity. First of all let us adopt standard notation, in binomial coefficients and Stirling numbers it is usually $n$ that indexes the size of the set being partitioned, so your identity becomes $$G(z) = \sum_{n\ge k} {n \brace k} z^n = \frac{z^k}{(1-z)(1-2z)\cdots(1-kz)}$$ i.e. the ordinary generating function of the number of set partitions of $n$ labelled elements into $k$ nonempty subsets. This is unusual because we normally would associate Stirling numbers of the second kind with exponential rather than ordinary generating functions.

First we use induction to show that $$\frac{z^k}{(1-z)(1-2z)\cdots(1-kz)} = \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\choose j} \frac{1}{1-jz}.$$ Setting $k=1$ gives $$\frac{z}{1-z} = -1 + \frac{1}{1-z}$$ which holds trivially. Now using induction we get that $$\frac{z^{k+1}}{(1-z)(1-2z)\cdots(1-kz)(1-(k+1)z)} = \frac{z}{1-(k+1)z} \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\choose j} \frac{1}{1-jz}.$$ But we have $$\frac{z}{1-(k+1)z} \frac{1}{1-jz} = \frac{1}{k+1-j} \frac{1}{1-(k+1)z} - \frac{1}{k+1-j} \frac{1}{1-jz}$$ as is easily seen because $$\frac{1}{k+1-j} (1-jz-(1-(k+1)z)) = \frac{1}{k+1-j} (k+1-j)z = z.$$ Returning to the sum from the induction we thus obtain $$\frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\choose j} \frac{1}{k+1-j} \left(\frac{1}{1-(k+1)z} - \frac{1}{1-jz}\right).$$ We now treat the two terms appearing in the difference in the sum in turn. For the first term which does not depend on $j$ we get that the coefficient on $1/(1-(k+1)z)$ is $$\frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\choose j} \frac{1}{k+1-j} = \frac{1}{(k+1)!} \sum_{j=0}^k (-1)^{k-j} {k+1\choose j} \\ = - \frac{1}{(k+1)!} \sum_{j=0}^k (-1)^{k+1-j} {k+1\choose j} = - \frac{1}{(k+1)!} \left(- (-1)^{k+1-(k+1)} {k+1\choose k+1}\right) = \frac{1}{(k+1)!}.$$ For the second term we get the sum $$- \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\choose j} \frac{1}{k+1-j} \frac{1}{1-jz} = - \frac{1}{(k+1)!} \sum_{j=0}^k (-1)^{k-j} {k+1\choose j} \frac{1}{1-jz} \\ = \frac{1}{(k+1)!} \sum_{j=0}^k (-1)^{k+1-j} {k+1\choose j} \frac{1}{1-jz}.$$ Summing the two contributions we obtain $$\frac{1}{(k+1)!} \sum_{j=0}^k (-1)^{k+1-j} {k+1\choose j} \frac{1}{1-jz} + \frac{1}{(k+1)!} \frac{1}{1-(k+1)z}$$ which is $$\frac{1}{(k+1)!} \sum_{j=0}^{k+1} (-1)^{k+1-j} {k+1\choose j} \frac{1}{1-jz}.$$ This completes the proof by induction.

Now we expand the rational term in the sum into an infinite series, getting $$\frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\choose j} \frac{1}{1-jz} = \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\choose j} \sum_{n\ge 0} j^n z^n\\ = \sum_{n\ge 0} z^n \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\choose j} j^n.$$

But we have $$ \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\choose j} j^n = {n\brace k}$$ by definition, thus completing the proof.

share|improve this answer
1  
Yes, but he said he already knew a proof, and was looking for a simple combinatorial interpretation ... –  Old John Nov 15 '13 at 22:35
1  
The algebraic proof is for the curious. Now that we have some activity on the question maybe someone e.g. Brian Scott who seems to have a gift for such things will post a combinatorial proof. –  Marko Riedel Nov 15 '13 at 22:43
add comment

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.