Some Stirling Number identities by differentiation

Wildon's Weblog 2018-03-12

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.