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)

    “Individually, museums are fine institutions, dedicated to the high values of preservation, education and truth; collectively, their growth in numbers points to the imaginative death of this country.”
    —Robert Hewison (b. 1943)

    “Give me a sentence which no intelligence can understand. There must be a kind of life and palpitation to it, and under its words a kind of blood must circulate forever.”
    —Henry David Thoreau (1817–1862)