The use of
exponential generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary ser ...
s (EGFs) to study the properties of
Stirling numbers
In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book ''Methodus differentialis'' (1730). They were redisco ...
is a classical exercise in
combinatorial mathematics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
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
formal power series
In mathematics, a formal series is an infinite sum that is considered independently from any notion of convergence, and can be manipulated with the usual algebraic operations on series (addition, subtraction, multiplication, division, partial s ...
, 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
*
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...
s (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.
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
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 mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary ser ...
:
:
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. ''B''
''n'' where
:
i.e. the
Bell number
In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of epony ...
s. The
Flajolet–Sedgewick fundamental theorem applies (labelled case).
The set
of partitions into non-empty subsets is given by ("set of non-empty sets of singletons")
:
This decomposition is entirely analogous to the construction of the set
of permutations from cycles, which is given by
:
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 function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary ser ...
s and because differentiating an EGF drops the first coefficient and shifts ''B''
''n''+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
, giving
:
Translating to generating functions, we obtain
:
This EGF yields the formula for the Stirling numbers of the second kind:
:
or
:
which simplifies to
:
References
*
Ronald Graham
Ronald Lewis Graham (October 31, 1935July 6, 2020) was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He ...
,
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer ...
,
Oren Patashnik
Oren Patashnik (born 1954) is an American computer scientist. He is notable for co-creating BibTeX, and co-writing '' Concrete Mathematics: A Foundation for Computer Science''. He is a researcher at the Center for Communications Research, La Jol ...
(1989): ''Concrete Mathematics'', Addison–Wesley,
*
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
Milton Abramowitz (19 February 1915 in Brooklyn, New York – 5 July 1958) was a Jewish American mathematician at the National Bureau of Standards who, with Irene Stegun, edited a classic book of mathematical tables called '' Handbook of Mathemat ...
and
Irene A. Stegun
Irene Ann Stegun (February 9, 1919 – January 27, 2008) was an American mathematician at the National Bureau of Standards (NBS, now the National Institute of Standards and Technology) who edited a classic book of mathematical tables called '' ...
, ''Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables'', USGPO, 1964, Washington DC, {{ISBN, 0-486-61272-4
Enumerative combinatorics