Let be the exponential generating function enumerating a family of combinatorial objects. For example, is the e.g.f. enumerating cycles (there are cycles on ) and is the e.g.f enumerating non-empty sets. Then is the e.g.f. enumerating set partitions where each part carries a -structure. For example,
where the Bell Number is the number of set partitions of . We can keep track of the number of parts with a further variable. For example
where the (unsigned) Stirling Number of the First Kind is the number of permutations of having exactly disjoint cycles. Similarly
where the Stirling Number of the Second Kind is the number of set partitions of into exactly 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 is the e.g.f enumerating two-part set compositions where carries no extra structure and carries a -structure. For example, if is the number of derangements of then, since any permutation is uniquely determined by its set of fixed points and the derangement it induces on the remaining points, we have , giving
For another example, observe that the e.g.f enumerating the functions is
Each such function is uniquely determined by a pair where carries no extra structure, and carries a set composition of into parts. Therefore the e.g.f. for set compositions is
(Note this series is doubly exponential: the number of set compositions of into exactly parts is the coefficient of .) Since there are set compositions associated to each set partition into parts, we get
as claimed earlier.
Multiplication by an exponential series is closely related to binomial inversion. Let . Then
if and only if .
This gives a very quick and elementary proof of the derangements formula: enumerating permutations by their number of fixed points we have , so
now take the coefficient of to get
Let be the exponential generating function for -structures. We have seen that the weighted exponential generating function for -structured set partitions is
Differentiating times with respect to , dividing by , and then setting we get
Now is the exponential generating function for -structured set partitions into exactly parts, so, taking coefficients of , we get
where is the number of -structured set partitions of
This identity gives uniform proofs of two Stirling Number identities.
Taking to enumerate Stirling Numbers of the First Kind we have and so
where the final equality holds because the middle sum counts triples where is an -subset of , is a permutation of having exactly disjoint cycles and is a cycle on ; such triples are in obvious bijection with permutations of having exactly disjoint cycles.
Taking to enumerate Stirling Numbers of the Second Kind we have and , so
This, and the analogous identity for the Stirling Numbers of the First Kind, may be compared with
which follows from counting set partitions according to the size of the part containing .
The left-hand side of the general identity above counts -structured set partitions of having exactly 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 -subset of , a -structured set partition of into distinguished parts, and an (undistinguished) -structured set partition of . This gives fully bijective proofs of both identities. So maybe they are not so deep: that said, even the special case of the first, namely
seemed non-obvious to me.