The following question is a reference request concerning a derivation of the EGF for the Stirling numbers of the second kind by Power Group Enumeration / Burnside's Lemma, which is $$\sum_{n\ge 0} {n\brace k} \frac{z^n}{n!} = \frac{(\exp(z)-1)^k}{k!}.$$

The idea is very simple. The labelled set partitions that Stirling numbers count can be represented by placing one of $k$ colors into a row of $n$ adjacent slots, where $n$ is the set being partitioned and $k$ gives the number of components. Hence a color signals what set the value corresponding to the slot should belong to.

The value of ${n\brace k}$ is then given by the number of orbits under the power group action obtained by letting the group acting on the slots be the identity and the group acting on the colors be the symmetric group on $k$ elements $S_k.$ Now applying Burnside we see that the group acting on the slots consists of one element containing $n$ fixed points. The admissible assignments to these fixed points under a permutation $\beta$ acting on the colors are those that are fixed points of $\beta.$ If we have $q$ such fixed points we can obtain $q^n$ valid assignments to the slots under the identity permutation.

We thus require the cycle index of the symmetric group $Z(S_k)$ with the fixed points marked. Recall that the OGF of these cycle indices is obtained from the species $$ \mathfrak{P}(\mathcal{A_1}\mathfrak{C}_1(\mathcal{W}) + \mathcal{A_2}\mathfrak{C}_2(\mathcal{W}) + \mathcal{A_3}\mathfrak{C}_3(\mathcal{W}) + \cdots)$$ which gives $$\exp\left(a_1 w + a_2 \frac{w^2}{2} + a_3 \frac{w^3}{3} + \cdots \right).$$ Keeping only the marker on the fixed points we obtain $$G(w, v) = \exp\left(v w + \frac{w^2}{2} + \frac{w^3}{3} + \cdots\right) \\ = \exp\left(v w - w + \log\frac{1}{1-w}\right) = \frac{e^{-w}}{1-w} e^{vw}.$$

We now determine the transformation required of this generating function. A term $C v^q w^m$ must be transformed into $C q^n w^m.$ This gives $$\left.\left(v\frac{d}{dv}\right)^n G(w, v) \right|_{v=1}.$$

Observe however that this term is a generating function of colorings where the term $w^k$ indexes colorings of at most $k$ colors. That means we actually require the difference between the coefficients on $w^k$ and on $w^{k-1}.$ This finally yields the formula

$${n\brace k} = [w^k] (1-w) \left.\left(v\frac{d}{dv}\right)^n G(w, v) \right|_{v=1}.$$

Substituting the actual value of $G(w, v)$ and moving constants to the front we obtain $${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} \frac{z^n}{n!} = [w^k] e^{-w} \left.\sum_{n\ge 0} \frac{z^n}{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 + \frac{zq}{1!} + \frac{(zq)^2}{2!} + \frac{(zq)^3}{3!} + \cdots\right) \times v^q \times w^m = e^{zq} \times v^q \times w^m.$$

This yields for $P(z)$ that $${\large P(z) = [w^k] e^{-w} \left. e^{\exp(z)\times v \times w}\right|_{v=1}} \\= {\large [w^k] e^{-w} e^{\exp(z) w} = [w^k] e^{(\exp(z)-1) w}.}$$ So that finally $$\color{#A00}{P(z)= \frac{(\exp(z)-1)^k}{k!}}.$$ This concludes the proof.

The purpose of this post is to determine as precise a reference as possible for this proof, taking into account all aspects of the technique used. If a precedent with an exact match could be found that would be terrific.

Post Scriptum. There is an instructive example of Power Group Enumeration at this MSE link.


Your Answer

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

Browse other questions tagged or ask your own question.