en>Eastlaw: added Category:Conservation equations using HotCat

2012-06-27T02:53:48Z

added Category:Conservation equations using HotCat

New page

The use of '''[[exponential generating function]]s (EGFs)''' to study the properties of '''[[Stirling numbers]]''' is a classical exercise in [[combinatorics|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 <math>[z^n]</math> for [[formal power series]], as well as the (labelled) operators <math>\mathfrak{C}</math> (for cycles) and <math>\mathfrak{P}</math> (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]]s (for unsigned Stirling numbers of the first kind):

::<math> \mathcal{P} = \mathfrak{P}(\mathfrak{C}(\mathcal{Z})),</math>

and
* [[set partition]]s into non-empty subsets (for Stirling numbers of the second kind):

:: <math> \mathcal{B} = \mathfrak{P}(\mathfrak{P}_{\ge 1}(\mathcal{Z})),</math>
where <math>\mathcal{Z}</math> 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 <math>\mathcal{P}\,</math> of permutations is given by

:<math> \mathcal{P} = \mathfrak{P}(\mathcal{U} \mathfrak{C}(\mathcal{Z})), \, </math>

where the singletion <math>\mathcal{U}</math> marks cycles. This decomposition is examined in some detail on the page on the [[Random permutation statistics|statistics of random permutations]].

Translating to generating functions we obtain the mixed generating function of the unsigned Stirling numbers of the first kind:

:<math>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|\left[\begin{matrix} n \\ k \end{matrix}\right]\right| u^k \, \frac{z^n}{n!}.
</math>

Now the signed Stirling numbers of the first kind are obtained from the unsigned ones through the relation
:<math>\left[\begin{matrix} n \\ k \end{matrix}\right] =
(-1)^{n-k} \left|\left[\begin{matrix} n \\ k \end{matrix}\right]\right|.</math>
Hence the generating function <math>H(z, u)</math> of these numbers is
:<math> H(z, u) = G(-z, -u) =
\left(\frac{1}{1+z} \right)^{-u} = (1+z)^u =
\sum_{n=0}^\infty \sum_{k=0}^n
\left[\begin{matrix} n \\ k \end{matrix}\right] u^k \, \frac{z^n}{n!}.</math>

A variety of identities may be derived by manipulating this [[generating function]]:

:<math>(1+z)^u = \sum_{n=0}^\infty {u \choose n} z^n =
\sum_{n=0}^\infty \frac {z^n}{n!} \sum_{k=0}^n
\left[\begin{matrix} n \\ k \end{matrix}\right] u^k =
\sum_{k=0}^\infty u^k
\sum_{n=k}^\infty \frac {z^n}{n!}
\left[\begin{matrix} n \\ k \end{matrix}\right] =
e^{u\log(1+z)}.
</math>

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

:<math>\sum_{k=0}^n (-1)^k
\left[\begin{matrix} n \\ k \end{matrix}\right] =
(-1)^n n!.</math>

This formula holds because the exponential generating function of the sum is

:<math>H(z, -1) = \frac{1}{1+z}

\quad \mbox{and hence} \quad

n! [z^n] H(z, -1) = (-1)^n n!.</math>

===Infinite sums===
Some infinite sums include

:<math>\sum_{n=k}^\infty
\left[\begin{matrix} n \\ k \end{matrix}\right]
\frac{z^n}{n!} = \frac {\left(\log (1+z)\right)^k}{k!}
</math>

where <math>|z|<1</math> (the singularity nearest to <math>z=0</math>
of <math>\log (1+z)</math> is at <math>z=-1.</math>)

This relation holds because

:<math>[u^k] H(z, u) = [u^k] \exp \left( u \log (1+z) \right) =
\frac {\left(\log (1+z)\right)^k}{k!}.</math>

==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

:<math>B_n = \sum_{k=1}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\}
\mbox{ and } B_0 = 1,</math>

i.e. the [[Bell numbers]]. The [[Symbolic combinatorics#The Flajolet–Sedgewick fundamental theorem]] applies (labelled case).
The set <math>\mathcal{B}\,</math> of partitions into non-empty subsets is given by ("set of non-empty sets of singletons")

:<math> \mathcal{B} = \mathfrak{P}(\mathfrak{P}_{\ge 1}(\mathcal{Z})).</math>

This decomposition is entirely analogous to the construction of the set <math>\mathcal{P}\,</math> of permutations from cycles, which is given by

:<math> \mathcal{P} = \mathfrak{P}(\mathfrak{C}(\mathcal{Z})).</math>

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

:<math> B(z) = \exp \left(\exp z - 1\right).</math>

Differentiate to obtain

:<math> \frac{d}{dz} B(z) =
\exp \left(\exp z - 1\right) \exp z = B(z) \exp z,</math>

which implies that

:<math> B_{n+1} = \sum_{k=0}^n {n \choose k} B_k,</math>

by convolution of [[exponential generating function]]s and because differentiating an EGF drops the first coefficient and shifts ''B''''n''+1 to ''z'' ''n''/''n''<nowiki>!</nowiki>.

The EGF of the Stirling numbers of the second kind is obtained by marking every subset that goes into the partition with the term <math>\mathcal{U}\,</math>, giving

:<math> \mathcal{B} = \mathfrak{P}(\mathcal{U} \; \mathfrak{P}_{\ge 1}(\mathcal{Z})).</math>

Translating to generating functions, we obtain

:<math> B(z, u) = \exp \left(u \left(\exp z - 1\right)\right).</math>

This EGF yields the formula for the Stirling numbers of the second kind:

:<math> \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!}</math>

or
:<math>
n! [z^n] \frac{1}{k!} \sum_{j=0}^k {k \choose j} \exp(jz) (-1)^{k-j}
</math>

which simplifies to

:<math> \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.</math>

==External links==
* Philippe Flajolet and Robert Sedgewick, ''[http://algo.inria.fr/flajolet/Publications/FlSe02.ps.gz Analytic combinatorics – Symbolic combinatorics.]''

== References ==
* [[Ronald 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

[[Category:Enumerative combinatorics]]

Conservation form - Revision history

en>Eastlaw: added Category:Conservation equations using HotCat