Stirling Numbers and Exponential Generating Functions - Stirling Numbers of The First Kind

Stirling Numbers of The First Kind

The unsigned Stirling numbers of the first kind count the number of permutations of with k cycles. A permutation is a set of cycles, and hence the set of permutations is given by

where the singletion 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} \right) = \left(\frac{1}{1-z} \right)^u = \sum_{n=0}^\infty \sum_{k=0}^n \left|\left\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

\left = (-1)^{n-k} \left|\left\right|.

Hence the generating function of these numbers is

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 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 u^k = \sum_{k=0}^\infty u^k \sum_{n=k}^\infty \frac {z^n}{n!} \left = 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.

Read more about this topic:  Stirling Numbers And Exponential Generating Functions

Famous quotes containing the words stirling, numbers and/or kind:

    “Oh, if thy pride did not our joys control,
    What world of loving wonders shouldst thou see!
    For if I saw thee once transformed in me,
    Then in thy bosom I would pour my soul;”
    —William Alexander, Earl O Stirling (1580?–1640)

    “Think of the earth as a living organism that is being attacked by billions of bacteria whose numbers double every forty years. Either the host dies, or the virus dies, or both die.”
    —Gore Vidal (b. 1925)

    “I’m the kind of writer that people think other people are reading.”
    —V.S. (Vidiadhar Surajprasad)