In his lectures on enumerative combinatorics, Prof. Federico Ardila gives a homework. For a fixed natural $k$, he asks us to prove the identity:

$$\sum_{n \geq 0} S(n,k) z^n = \left(\frac{z}{1-z}\right)\left(\frac{z}{1-2z}\right)...\left(\frac{z}{1-kz}\right).$$

Here, $S(n,k)$ is the number of ways of partitioning a $n$-element set into $k$ sets.

I know the proof of the above identity using recursions. I also know combinatorial proofs of related identities. But I want to know the proof using combinatorial classes.

It looks like the combinatorial class of $k$-partitions is the product of the classes Seq({$0,1,2,...,l$}) from $l=0$ to $l=k-1$. But I am unable to find an such an interpretation.

How do I solve this problem?



The difficulty here is that you have an OGF where most commonly EGFs are used. Nonetheless a proof using unlabeled species and advanced Polya Enumeration can be given.

Some time ago I posted an intriguing result proving the EGF of the Stirling numbers ${n\brace k}$ with $k$ fixed which seems not to have found an audience. This is the MSE link.

We can use the material from this link without explicitly recapitulating everything as it is sound. The following formula was proved there by methods of species theory (unlabeled): $${n\brace k} = [w^k] e^{-w} \left.\left(v\frac{d}{dv}\right)^n e^{vw} \right|_{v=1}.$$

Introduce the generating function $$P(z) = \sum_{n\ge 0} {n\brace k} z^n = [w^k] e^{-w} \left.\sum_{n\ge 0} z^n \left(v\frac{d}{dv}\right)^n e^{vw} \right|_{v=1}.$$ Now the operator represented by the sum turns $v^q w^m$ into $$\left(1 + (zq) + (zq)^2 + (zq)^3 + \cdots\right) \times v^q \times w^m = \frac{1}{1-qz} \times v^q \times w^m.$$

Therefore $$e^{vw} = \sum_{q\ge 0} \frac{v^q w^q}{q!}$$ is transformed into $$\sum_{q\ge 0} \frac{1}{1-qz} \frac{v^q w^q}{q!}.$$

This yields for $P(z)$ that $$P(z) = [w^k] e^{-w} \left. \sum_{q\ge 0} \frac{1}{1-qz} \frac{v^q w^q}{q!} \right|_{v=1} = [w^k] e^{-w} \sum_{q\ge 0} \frac{1}{1-qz} \frac{w^q}{q!}.$$

Actually doing the coefficient extraction we obtain $$P(z) = \sum_{p=0}^k \frac{(-1)^{k-p}}{(k-p)!} \frac{1}{1-pz} \frac{1}{p!} = \frac{1}{k!} \sum_{p=0}^k {k\choose p} \frac{(-1)^{k-p}}{1-pz}.$$

Now to see that this is equal to $$Q(z) = \prod_{p=1}^k \frac{z}{1-pz}$$ we can use partial fractions by residues for rational functions, getting $$\mathrm{Res}_{z=1/m} Q(z) = \mathrm{Res}_{z=1/m} \frac{z/m}{1/m-z} \prod_{p=1}^{m-1} \frac{z}{1-pz} \prod_{p=m+1}^k \frac{z}{1-pz} \\ = -\frac{1}{m^2} \prod_{p=1}^{m-1} \frac{1/m}{1-p/m} \prod_{p=m+1}^k \frac{1/m}{1-p/m} \\ = -\frac{1}{m^2} \prod_{p=1}^{m-1} \frac{1}{m-p} \prod_{p=m+1}^k \frac{1}{m-p} = -\frac{1}{m^2} \frac{1}{(m-1)!} \frac{(-1)^{k-m}}{(k-m)!} \\ = -\frac{1}{m} \frac{1}{m!} \frac{(-1)^{k-m}}{(k-m)!}.$$

On the other hand $$\mathrm{Res}_{z=1/m} P(z) = \mathrm{Res}_{z=1/m} \frac{1}{k!} {k\choose m} \frac{(-1)^{k-m}}{1-mz} \\ = - \frac{1}{m} \mathrm{Res}_{z=1/m} \frac{1}{k!} {k\choose m} \frac{(-1)^{k-m}}{z-1/m} = -\frac{1}{m} \frac{1}{m!} \frac{(-1)^{k-m}}{(k-m)!}.$$

The residues are equal, all the poles are simple, the two functions are rational and have no other poles, hence we have equality. This concludes the proof.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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