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. This article uses the coefficient extraction operator [ z n ] {\displaystyle [z^{n}]} for formal power series, as well as the (labelled) operators C {\displaystyle {\mathfrak {C}}} (for cycles) and P {\displaystyle {\mathfrak {P}}} (for sets) on combinatorial classes, which are explained on the page for symbolic combinatorics. Given a combinatorial class, the cycle operator creates the class obtained by placing objects from the source class along a cycle of some length, where cyclical symmetries are taken into account, and the set operator creates the class obtained by placing objects from the source class in a set (symmetries from the symmetric group, i.e. an "unstructured bag".) The two combinatorial classes (shown without additional markers) are
permutations (for unsigned Stirling numbers of the first kind):
P = SET ( CYC ( Z ) ) , {\displaystyle {\mathcal {P}}=\operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}})),}
and
set partitions into non-empty subsets (for Stirling numbers of the second kind):
B = SET ( SET ≥ 1 ( Z ) ) , {\displaystyle {\mathcal {B}}=\operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})),}
where Z {\displaystyle {\mathcal {Z}}} is the singleton class. 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 P {\displaystyle {\mathcal {P}}\,} of permutations is given by
P = SET ( U × CYC ( Z ) ) , {\displaystyle {\mathcal {P}}=\operatorname {SET} ({\mathcal {U}}\times \operatorname {CYC} ({\mathcal {Z}})),\,}
where the singleton U {\displaystyle {\mathcal {U}}} marks cycles. This decomposition is examined in some detail on the page on the statistics of random permutations. Translating to generating functions we obtain the mixed generating function of the unsigned Stirling numbers of the first kind:
G ( z , u ) = exp ( u log 1 1 − z ) = ( 1 1 − z ) u = ∑ n = 0 ∞ ∑ k = 0 n [ n k ] u k z n n ! . {\displaystyle G(z,u)=\exp \left(u\log {\frac {1}{1-z}}\right)=\left({\frac {1}{1-z}}\right)^{u}=\sum _{n=0}^{\infty }\sum _{k=0}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}\,{\frac {z^{n}}{n!}}.}
Now the signed Stirling numbers of the first kind are obtained from the unsigned ones through the relation
( − 1 ) n − k [ n k ] . {\displaystyle (-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right].}
Hence the generating function H ( z , u ) {\displaystyle H(z,u)} of these numbers is
… excerpt ends here. Continue reading the full article.
