This article uses the coefficient extraction operator for formal power series, as well as the (labelled) operators (for cycles) and (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):
and
set partitions into non-empty subsets (for Stirling numbers of the second kind):
where 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.
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 of permutations is given by
where the singleton 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:
Now the signed Stirling numbers of the first kind are obtained from the unsigned ones through the relation
Hence the generating function of these numbers is
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 (the singularity nearest to of is at )
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
D. S. Mitrinovic, Sur une classe de nombre relies aux nombres de Stirling, C. R. Acad. Sci. Paris 252 (1961), 2354–2356.
A. C. R. Belton, The monotone Poisson process, in: Quantum Probability (M. Bozejko, W. Mlotkowski and J. Wysoczanski, eds.), Banach Center Publications 73, Polish Academy of Sciences, Warsaw, 2006
stirling, numbers, exponential, generating, functions, symbolic, combinatorics, exponential, generating, functions, egfs, study, properties, stirling, numbers, classical, exercise, combinatorial, mathematics, possibly, canonical, example, symbolic, combinatori. 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 dd 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 dd 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 Contents 1 Stirling numbers of the first kind 1 1 Finite sums 1 2 Infinite sums 2 Stirling numbers of the second kind 3 ReferencesStirling numbers of the first kind EditThe 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 H z u G z u 1 1 z u 1 z u n 0 k 0 n 1 n k n k u k z n n displaystyle H z u G z u left frac 1 1 z right u 1 z u sum n 0 infty sum k 0 n 1 n k left begin matrix n k end matrix right u k frac z n n A variety of identities may be derived by manipulating this generating function 1 z u n 0 u n z n n 0 z n n k 0 n 1 n k n k u k k 0 u k n k z n n 1 n k n k e u log 1 z displaystyle 1 z u sum n 0 infty u choose n z n sum n 0 infty frac z n n sum k 0 n 1 n k left begin matrix n k end matrix right u k sum k 0 infty u k sum n k infty frac z n n 1 n k left begin matrix n k end matrix right e u log 1 z In particular the order of summation may be exchanged and derivatives taken and then z or u may be fixed Finite sums Edit A simple sum is k 0 n 1 k n k 1 n n displaystyle sum k 0 n 1 k left begin matrix n k end matrix right 1 n n This formula holds because the exponential generating function of the sum is H z 1 1 1 z and hence n z n H z 1 1 n n displaystyle H z 1 frac 1 1 z quad mbox and hence quad n z n H z 1 1 n n Infinite sums Edit Some infinite sums include n k n k z n n log 1 z k k displaystyle sum n k infty left begin matrix n k end matrix right frac z n n frac left log 1 z right k k where z lt 1 displaystyle z lt 1 the singularity nearest to z 0 displaystyle z 0 of log 1 z displaystyle log 1 z is at z 1 displaystyle z 1 This relation holds because u k H z u u k exp u log 1 z log 1 z k k displaystyle u k H z u u k exp left u log 1 z right frac left log 1 z right k k Stirling numbers of the second kind EditThese numbers count the number of partitions of n into k nonempty subsets First consider the total number of partitions i e Bn where B n k 1 n n k and B 0 1 displaystyle B n sum k 1 n left begin matrix n k end matrix right mbox and B 0 1 i e the Bell numbers The Flajolet Sedgewick fundamental theorem applies labelled case The set B displaystyle mathcal B of partitions into non empty subsets is given by set of non empty sets of singletons B SET SET 1 Z displaystyle mathcal B operatorname SET operatorname SET geq 1 mathcal Z This decomposition is entirely analogous to the construction of the set P displaystyle mathcal P of permutations from cycles which is given by P SET CYC Z displaystyle mathcal P operatorname SET operatorname CYC mathcal Z 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 B z exp exp z 1 displaystyle B z exp left exp z 1 right Differentiate to obtain d d z B z exp exp z 1 exp z B z exp z displaystyle frac d dz B z exp left exp z 1 right exp z B z exp z which implies that B n 1 k 0 n n k B k displaystyle B n 1 sum k 0 n n choose k B k 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 U displaystyle mathcal U giving B SET U SET 1 Z displaystyle mathcal B operatorname SET mathcal U times operatorname SET geq 1 mathcal Z Translating to generating functions we obtain B z u exp u exp z 1 displaystyle B z u exp left u left exp z 1 right right This EGF yields the formula for the Stirling numbers of the second kind n k n u k z n B z u n z n exp z 1 k k displaystyle left begin matrix n k end matrix right n u k z n B z u n z n frac exp z 1 k k or n z n 1 k j 0 k k j exp j z 1 k j displaystyle n z n frac 1 k sum j 0 k k choose j exp jz 1 k j which simplifies to n k j 0 k k j 1 k j j n n 1 k j 0 k k j 1 k j j n displaystyle frac n k sum j 0 k k choose j 1 k j frac j n n frac 1 k sum j 0 k k choose j 1 k j j n References EditRonald Graham Donald Knuth Oren Patashnik 1989 Concrete Mathematics Addison Wesley ISBN 0 201 14236 8 D S Mitrinovic Sur une classe de nombre relies aux nombres de Stirling C R Acad Sci Paris 252 1961 2354 2356 A C R Belton The monotone Poisson process in Quantum Probability M Bozejko W Mlotkowski and J Wysoczanski eds Banach Center Publications 73 Polish Academy of Sciences Warsaw 2006 Milton Abramowitz and Irene A Stegun Handbook of Mathematical Functions with Formulas Graphs and Mathematical Tables USGPO 1964 Washington DC ISBN 0 486 61272 4 Retrieved from https en wikipedia org w index php title Stirling numbers and exponential generating functions in symbolic combinatorics amp oldid 1107687928, wikipedia, wiki, book, books, library,