Stirling numbers and exponential generating functions

Stirling numbers and exponential generating functions

The use of exponential generating functions or EGFs to study the properties of Stirling numbers is a classical exercise in combinatorics and possibly the canonical example of how symbolic combinatorics, the method that encapsulates the fundamental theorem of combinatorial enumeration, 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] for formal power series, as well as the (labelled) operators mathfrak{C} (for cycles) and mathfrak{P} (for sets) on combinatorial classes, which are explained on the pages for symbolic combinatorics and the fundamental theorem of combinatorial enumeration. Quite simply, 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):

:: mathcal{P} = mathfrak{P}(mathfrak{C}(mathcal{Z})),

and
* set partitions into non-empty subsets (for Stirling numbers of the second kind):

:: mathcal{B} = mathfrak{P}(mathfrak{P}_{ge 1}(mathcal{Z})),where mathcal{Z} is the singleton class.

tirling 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 mathcal{P}, of permutations is given by: mathcal{P} = mathfrak{P}(mathcal{U} mathfrak{C}(mathcal{Z})),where the singletion 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 left( u log frac{1}{1-z} ight) =left(frac{1}{1-z} ight)^u =sum_{n=0}^infty sum_{k=0}^n left|left [egin{matrix} n \ k end{matrix} ight] ight| u^k , frac{z^n}{n!}.

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

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

:(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 [egin{matrix} n \ k end{matrix} ight] u^k = sum_{k=0}^infty u^ksum_{n=k}^infty frac {z^n}{n!}left [egin{matrix} n \ k end{matrix} ight] = e^{ulog(1+z)}.

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

:sum_{k=0}^n (-1)^k left [egin{matrix} n \ k end{matrix} ight] = (-1)^n n!.

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

:H(z, -1) = frac{1}{1+z}

quad mbox{and hence} quad

n! [z^n] H(z, -1) = (-1)^n n!.

A convolution identity

The identity:sum_{p=k}^{n}{left|left [egin{matrix} n \ p end{matrix} ight] ight
inom{p}{k=left|left [egin{matrix} n+1 \ k+1 end{matrix} ight] ight|has a combinatorial proof as well as a proof using generating functions. The left side counts permutations of "n" elements, with at least "k" cycles, of which exactly "k" are marked. The right side counts permutations of n+1 elements having exactly k+1 cycles. It is easy to establish a bijection between these two, thereby showing that they have the same cardinality. To go from the left to the right, take the cycles that were not marked, which define a permutation, write down this permutation in table notation, i.e. as a sequence, and make it into a cycle by connecting the end of the table to the beginning, inserting n+1 after the end, thereby obtaining a permutation on n+1 elements having exactly k+1 cycles. The other direction is as follows: mark all cycles except the one containing n+1, then take this cycle (the one that contains n+1) and turn it into a sequence by taking it apart at the position of n+1, which you remove. Read this sequence as a permutation and factorize it into cycles. You now have a permutation on [1, n] of at least "k" cycles, of which exactly "k" are marked. As an example, let n=8 and suppose you have not marked (1 8) (2 5). Written in table notation, this reads [8 5 2 1] . Turn it into a cycle, inserting n+1 = 9, getting (8 5 2 1 9).

The proof using generating functions follows directly from the generating function G(z, u).,

We have:left|left [egin{matrix} n+1 \ k+1 end{matrix} ight] ight
= (n+1)! [z^{n+1}] [u^{k+1}] left( frac{1}{1-z} ight)^u.

Differentiating with respect to "z", we find:left|left [egin{matrix} n+1 \ k+1 end{matrix} ight] ight
= n! [z^n] [u^{k+1}] frac{u}{1-z} left( frac{1}{1-z} ight)^u= n! [z^n] [u^k] left( frac{1}{1-z} ight)^{u+1}.

Note that:left( frac{1}{1-z} ight)^{u+1} =sum_{pge 0} frac{(u+1)^p}{p!} left( log frac{1}{1-z} ight)^p,so that:left|left [egin{matrix} n+1 \ k+1 end{matrix} ight] ight
= n! [z^n] sum_{pge k} inom{p}{k} frac{1}{p!} left( log frac{1}{1-z} ight)^p,which is: n! [z^n] sum_{pge k} inom{p}{k} [u^p] G(z, u)= sum_{pge k} inom{p}{k} n! [z^n] [u^p] G(z, u) = sum_{pge k} inom{p}{k} left|left [egin{matrix} n \ p end{matrix} ight] ight|.But:left|left [egin{matrix} n \ p end{matrix} ight] ight| = 0quad mbox{when} quad p>n,so this simplifies to:left|left [egin{matrix} n+1 \ k+1 end{matrix} ight] ight
= sum_{p=k}^n left|left [egin{matrix} n \ p end{matrix} ight] ight
inom{p}{k}, quad mbox{QED}.

The references for this identity are from "sci.math.research", more information may be found here.

Infinite sums

Some infinite sums include

:sum_{n=k}^infty left [egin{matrix} n \ k end{matrix} ight] frac{z^n}{n!} = frac {left(log (1+z) ight)^k}{k!}

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

This relation holds because

: [u^k] H(z, u) = [u^k] exp left( u log (1+z) ight) =frac {left(log (1+z) ight)^k}{k!}.

tirling 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

:B_n = sum_{k=1}^n left{egin{matrix} n \ k end{matrix} ight}mbox{ and } B_0 = 1,

i.e. the Bell numbers. The fundamental theorem of combinatorial enumeration applies (labelled case).The set mathcal{B}, of partitions into non-empty subsets is given by("set of non-empty sets of singletons")

: mathcal{B} = mathfrak{P}(mathfrak{P}_{ge 1}(mathcal{Z})).

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

: mathcal{P} = mathfrak{P}(mathfrak{C}(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 left(exp z - 1 ight).

Differentiate to obtain

: frac{d}{dz} B(z) = exp left(exp z - 1 ight) exp z = B(z) exp z,

which implies that

: 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 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 mathcal{U},, giving

: mathcal{B} = mathfrak{P}(mathcal{U} ; mathfrak{P}_{ge 1}(mathcal{Z})).

Translating to generating functions, we obtain

: B(z, u) = exp left(u left(exp z - 1 ight) ight).

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

: left{egin{matrix} n \ k end{matrix} ight} =n! [u^k] [z^n] B(z, u) =n! [z^n] frac{(exp z - 1)^k}{k!}

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

which simplifies to

: 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.

We can use B(z, u) to evaluate the sum

: sum_{k=0}^n left{egin{matrix} n \ k end{matrix} ight} (x)_k.

This is equal to

: sum_{k=0}^n n! [u^k] [z^n] B(z, u) (x)_k =n! [z^n] sum_{k=0}^n [u^k] B(z, u) (x)_k

or

:n! [z^n] sum_{k=0}^n frac{(exp z - 1)^k}{k!} (x)_k= n! [z^n] sum_{k=0}^infty frac{(exp z - 1)^k}{k!} (x)_k

where the last equality occurs because [z^n] (exp z - 1)^k = 0, when n

Now consider the Taylor series of y^x at y=1:

: y^x =sum_{k=0}^infty left( left(frac{d}{dy} ight)^k y^x Bigg|_{y=1} ight) frac{(y-1)^k}{k!} =sum_{k=0}^infty (x)_k frac{(y-1)^k}{k!}.

Hence

: sum_{k=0}^n left{egin{matrix} n \ k end{matrix} ight} (x)_k =n! [z^n] exp(xz) = n! frac{x^n}{n!} = x^n.

External links

* Philippe Flajolet and Robert Sedgewick, " [http://algo.inria.fr/flajolet/Publications/FlSe02.ps.gz Analytic combinatorics - Symbolic combinatorics.] "
* Various, " [http://groups.google.com/group/sci.math.research/browse_thread/thread/d93538abc2031d70/79cf8ef785047035#79cf8ef785047035 Identity for unsigned Stirling Numbers of the first kind] , newsgroup sci.math.research"

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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Stirling numbers of the first kind — In mathematics, Stirling numbers of the first kind, together with the Stirling numbers of the second kind, are one of the two types of Stirling numbers. They commonly occur in the study of combinatorics, where they count the number of… …   Wikipedia

  • Stirling number — In mathematics, Stirling numbers arise in a variety of combinatorics problems. They are named after James Stirling, who introduced them in the 18th century. Two different sets of numbers bear this name: the Stirling numbers of the first kind and… …   Wikipedia

  • Symbolic combinatorics — in mathematics is a technique of analytic combinatorics that uses symbolic representations of combinatorial classes to derive their generating functions. The underlying mathematics, including the Pólya enumeration theorem, are explained on the… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Random permutation statistics — The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example,… …   Wikipedia

  • Binomial coefficient — The binomial coefficients can be arranged to form Pascal s triangle. In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the… …   Wikipedia

  • mathematics — /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… …   Universalium

  • Harmonic number — The term harmonic number has multiple meanings. For other meanings, see harmonic number (disambiguation) .In mathematics, the n th harmonic number is the sum of the reciprocals of the first n natural numbers::H n=… …   Wikipedia

  • Binomial transform — In combinatorial mathematics the binomial transform is a sequence transformation (ie, a transform of a sequence) that computes its forward differences. It is closely related to the Euler transform, which is the result of applying the binomial… …   Wikipedia

  • Timeline of mathematics — A timeline of pure and applied mathematics history. Contents 1 Before 1000 BC 2 1st millennium BC 3 1st millennium AD 4 1000–1500 …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”