# Getting the proof of the generating function formula for Stirling numbers by 'staring' at the expression using combinatorial classes.

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?

Thanks.

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.