The use of exponential generating functions (EGFs) to study the properties of Stirling numbers is a classical exercise in combinatorial mathematics and possibly the canonical example of how symbolic combinatorics is used. It also illustrates the parallels in the construction of these two types of numbers, lending support to the binomial-style notation that is used for them.
Contents
- Stirling numbers of the first kind
- Finite sums
- Infinite sums
- Stirling numbers of the second kind
- References
This article uses the coefficient extraction operator
and
where
Warning: The notation used here for the Stirling numbers is not that of the Wikipedia articles on Stirling numbers; square brackets denote the signed Stirling numbers here.
Stirling numbers of the first kind
The unsigned Stirling numbers of the first kind count the number of permutations of [n] with k cycles. A permutation is a set of cycles, and hence the set
where the singleton
Translating to generating functions we obtain the mixed generating function of the unsigned Stirling numbers of the first kind:
Now the signed Stirling numbers of the first kind are obtained from the unsigned ones through the relation
Hence the generating function
A variety of identities may be derived by manipulating this generating function:
In particular, the order of summation may be exchanged, and derivatives taken, and then z or u may be fixed.
Finite sums
A simple sum is
This formula holds because the exponential generating function of the sum is
Infinite sums
Some infinite sums include
where
This relation holds because
Stirling numbers of the second kind
These numbers count the number of partitions of [n] into k nonempty subsets. First consider the total number of partitions, i.e. Bn where
i.e. the Bell numbers. The Flajolet–Sedgewick fundamental theorem applies (labelled case). The set
This decomposition is entirely analogous to the construction of the set
and yields the Stirling numbers of the first kind. Hence the name "Stirling numbers of the second kind."
The decomposition is equivalent to the EGF
Differentiate to obtain
which implies that
by convolution of exponential generating functions and because differentiating an EGF drops the first coefficient and shifts Bn+1 to z n/n!.
The EGF of the Stirling numbers of the second kind is obtained by marking every subset that goes into the partition with the term
Translating to generating functions, we obtain
This EGF yields the formula for the Stirling numbers of the second kind:
or
which simplifies to