Some Stirling Number identities by differentiation

Let G(z) be the exponential generating function enumerating a family of combinatorial objects. For example, -\log(1-z) = \sum_{n=1}^\infty z^n/n is the e.g.f. enumerating cycles (there are (n-1)! cycles on \{1,\ldots,n\}) and \mathrm{e}^z -1 = \sum_{n=1}^\infty z^n/n! is the e.g.f enumerating non-empty sets. Then \exp G(z) is the e.g.f. enumerating set partitions where each part carries a G-structure. For example,

\exp (\mathrm{e}^z - 1) = \sum_{n=0}^\infty B_n \frac{z^n}{n!}

where the Bell Number B_n is the number of set partitions of \{1,\ldots, n\}. We can keep track of the number of parts with a further variable. For example

\exp \bigl( -x \log (1-z) \bigr) = \sum_{n=0}^\infty \sum_{m=0}^\infty \genfrac{[}{]}{0pt}{}{n}{m} x^m \frac{z^n}{n!}

where the (unsigned) Stirling Number of the First Kind \genfrac{[}{]}{0pt}{}{n}{m} is the number of permutations of \{1, \ldots, n\} having exactly m disjoint cycles. Similarly

\exp \bigl( x(\mathrm{e}^z - 1) \bigr) = \sum_{n=0}^\infty \sum_{m=0}^\infty \genfrac{\{}{\}}{0pt}{}{n}{m} x^m \frac{z^n}{n!}

where the Stirling Number of the Second Kind \genfrac{\{}{\}}{0pt}{}{n}{m} is the number of set partitions of \{1, \ldots, n\} into exactly m parts.

All this is explained beautifully in Chapter 3 of Wilf’s book generating functionology, in a way that leads readily into the high-brow modern take on these ideas using combinatorial species. For my planned combinatorics textbook I expect to deal with products of exponential generating functions in an ad-hoc way, and probably not do much more, since it’s impossible to compete with Wilf’s exposition.

Two part structures where one part is boring

A special case of the multiplication rule is that \exp(z) G(z) is the e.g.f enumerating two-part set compositions (A,B) where A carries no extra structure and B carries a G-structure. For example, if d_n is the number of derangements of \{1,\ldots, n\} then, since any permutation is uniquely determined by its set of fixed points and the derangement it induces on the remaining points, we have \exp(z) G(z) = \sum_{n=0}^\infty n! z^n/n! = 1/(1-z), giving

G(z) = \exp(-z)/(1-z).

For another example, observe that the e.g.f enumerating the r^n functions f : \{1,\ldots, n\} \rightarrow \{1,\ldots, r\} is

\sum_{r=0}^\infty r^n \frac{w^r}{r!} \frac{z^n}{n!} = \sum_{r=0}^\infty \frac{w^r}{r!} \sum_{n=0}^\infty \frac{(rz)^n}{n!} = \sum_{r=0}^\infty \frac{w^r}{r!} \mathrm{e}^{rz} = \exp (w \mathrm{e}^z).

Each such function is uniquely determined by a pair (A,B) where A = \{1,\ldots,r\} \backslash \mathrm{im} f carries no extra structure, and B = \mathrm{im} f carries a set composition of \{1,\ldots, n\} into |B| parts. Therefore the e.g.f. for set compositions is

\exp(-w) \exp (w\mathrm{e}^z) = \exp(w (\mathrm{e}^z-1)).

(Note this series is doubly exponential: the number of set compositions of \{1,\ldots,n\} into exactly m parts is the coefficient of w^m/m! z^n/n!.) Since there are m! set compositions associated to each set partition into m parts, we get

\exp(w (\mathrm{e}^z-1) = \sum_{s=0}^\infty \sum_{n=0}^\infty \genfrac{\{}{\}}{0pt}{}{n}{m} w^m \frac{z^n}{n!}.

as claimed earlier.

Binomial inversion

Multiplication by an exponential series is closely related to binomial inversion. Let G(z) = \sum_{n=0}^\infty a_n z^n/n!. Then

\exp(z) G(z) = \sum_{n=0}^\infty b_n z^n/n!

if and only if b_n = \sum_{m=0}^n \binom{n}{m} a_m.

This gives a very quick and elementary proof of the derangements formula: enumerating permutations by their number of fixed points we have n! = \sum_{m=0}^n \binom{n}{m} d_m, so

\sum_{n=0}^\infty d_n z^n/n! = \exp(-z) \sum_{n=0}^\infty n! z^n/n! = \exp(-z)/(1-z);

now take the coefficient of z^n to get

d_n = n!\bigl( 1-\frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!} \bigr).

Differentiation

Let G(z) = \sum_{n=1}^\infty a_n z^n/n! be the exponential generating function for G-structures. We have seen that the weighted exponential generating function for G-structured set partitions is

\sum_{m=0}^\infty \sum_{n=0}^\infty a^{(m)}_n x^m \frac{z^n}{n!} = \exp x G(z).

Differentiating k times with respect to x, dividing by k!, and then setting x=1 we get

\sum_{n=0}^\infty \sum_{m=0}^n a^{(m)}_n \binom{m}{k} \frac{z^n}{n!} = G(z)^k/k! \exp G(z).

Now G(z)^k/k! is the exponential generating function for G-structured set partitions into exactly k parts, so, taking coefficients of z^n/n!, we get

\begin{aligned} \sum_{m=0}^n a^{(m)}_n \binom{m}{k} &= \Bigl[ \frac{z^n}{n!}\Bigr] \sum_{r=0}^\infty a^{(k)}_r \frac{z^r}{r!} \exp G(z) \\ &= \sum_{r=0}^n a^{(k)}_r \frac{n!}{r!} [z^{n-r}] \exp G(z) \\ &= \sum_{r=0}^n \binom{n}{r} a^{(k)}_r \bigl[\frac{z^{n-r}}{(n-r)!}\Bigr] \exp G(z) \\ &= \sum_{r=0}^n \binom{n}{r} a^{(k)}_r b_{n-r} \end{aligned}

where b_n is the number of G-structured set partitions of \{1,\ldots,n\}.

This identity gives uniform proofs of two Stirling Number identities.

Taking G(z) = -\log (1-z) to enumerate Stirling Numbers of the First Kind we have \exp G(z) = 1/(1-z) and b_n = n! so

\sum_{m=0}^n \genfrac{[}{]}{0pt}{}{n}{m} \binom{m}{k} = \sum_{r=0}^n \binom{n}{r} \genfrac{[}{]}{0pt}{}{r}{k} (n-r)! = \genfrac{[}{]}{0pt}{}{n+1}{k+1}

where the final equality holds because the middle sum counts triples (X, \sigma, \tau) where X is an r-subset of \{1,\ldots, n\}, \sigma is a permutation of X having exactly k disjoint cycles and \tau is a cycle on \{1,\ldots,n,n+1\}\backslash X; such triples are in obvious bijection with permutations of \{1,\ldots,n ,n+1\} having exactly k+1 disjoint cycles.

Taking G(z) = \mathrm{e}^z-1 to enumerate Stirling Numbers of the Second Kind we have \exp G(z) = \sum_{n=0}^\infty B_n \frac{z^n}{n!} and b_n = B_n, so

\sum_{m=0}^n \genfrac{\{}{\}}{0pt}{}{n}{m} \binom{m}{k} = \sum_{r=0}^n \binom{n}{r} \genfrac{\{}{\}}{0pt}{}{r}{k} B_{n-r}.

This, and the analogous identity for the Stirling Numbers of the First Kind, may be compared with

\sum_{m=0}^n \binom{n}{m} \genfrac{\{}{\}}{0pt}{}{m}{k} = \genfrac{\{}{\}}{0pt}{}{n+1}{k+1}

which follows from counting set partitions according to the size of the part containing n+1.

Bijective proofs

The left-hand side of the general identity above counts G-structured set partitions of \{1,\ldots,n\} having exactly k distinguished parts, and maybe some further undistinguished parts. (Typically differentiation transforms generating functions in this way). The right-hand side counts the same objects, by enumerating triples consisting of an r-subset X of \{1,\ldots,n\}, a G-structured set partition of X into k distinguished parts, and an (undistinguished) G-structured set partition of \{1,\ldots,n\}\backslash X. This gives fully bijective proofs of both identities. So maybe they are not so deep: that said, even the special case k=1 of the first, namely

\sum_{m=0}^n \genfrac{[}{]}{0pt}{}{n}{m} m = \genfrac{[}{]}{0pt}{}{n+1}{2}

seemed non-obvious to me.

This entry was posted on Monday, March 20th, 2017 at 6:46 pm and is filed under Combinatorics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a comment