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?


2 Answers 2


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:


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.

  • 5
    $\begingroup$ 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. $\endgroup$ Nov 18, 2013 at 1:49
  • 1
    $\begingroup$ @MarkoRiedel That is precisely it! :) $\endgroup$ Nov 18, 2013 at 1:54
  • 1
    $\begingroup$ These are sometimes called "rhyming schemes": en.wikipedia.org/wiki/… $\endgroup$
    – user940
    Nov 18, 2013 at 2:06
  • $\begingroup$ Beautiful (and relevant) answer ! (+1) $\endgroup$ Jan 23, 2023 at 10:15

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.

Addendum. An alternative proof uses residues. We write

$$\frac{z^k}{(1-z)(1-2z)\cdots(1-kz)} = \frac{1}{(1/z-1)(1/z-2)\cdots(1/z-k)} \\ = \frac{1}{(w-1)(w-2)\cdots(w-k)}.$$

This is

$$\sum_{j=1}^k \frac{1}{w-j} \mathrm{Res}_{w=j} \frac{1}{(w-1)(w-2)\cdots(w-k)} \\ = \sum_{j=1}^k \frac{1}{w-j} \prod_{q=1}^{j-1} \frac{1}{j-q} \prod_{q=j+1}^k \frac{1}{j-q} = \sum_{j=1}^k \frac{1}{w-j} \frac{1}{(j-1)!} \frac{(-1)^{k-j}}{(k-j)!} \\ = \frac{1}{k!} \sum_{j=1}^k \frac{j}{w-j} \frac{k!}{j!} \frac{(-1)^{k-j}}{(k-j)!} = \frac{1}{k!} \sum_{j=1}^k (-1)^{k-j} {k\choose j} \frac{j}{w-j}.$$

With $w=1/z$ and extracting the coefficient on $[z^n]$ this becomes

$$[z^n] \frac{1}{k!} \sum_{j=1}^k (-1)^{k-j} {k\choose j} \frac{jz}{1-jz} = \frac{1}{k!} \sum_{j=1}^k (-1)^{k-j} {k\choose j} j [z^{n-1}] \frac{1}{1-jz} \\ = \frac{1}{k!} \sum_{j=1}^k (-1)^{k-j} {k\choose j} j^n = \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\choose j} j^n = {n\brace k}.$$

  • 5
    $\begingroup$ Yes, but he said he already knew a proof, and was looking for a simple combinatorial interpretation ... $\endgroup$
    – Old John
    Nov 15, 2013 at 22:35
  • 4
    $\begingroup$ 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. $\endgroup$ Nov 15, 2013 at 22:43
  • $\begingroup$ Beautiful (and very relevant to the needs of the MO) answer ! (+1) $\endgroup$ Jan 23, 2023 at 10:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .