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)

    “All experience teaches that, whenever there is a great national establishment, employing large numbers of officials, the public must be reconciled to support many incompetent men; for such is the favoritism and nepotism always prevailing in the purlieus of these establishments, that some incompetent persons are always admitted, to the exclusion of many of the worthy.”
    —Herman Melville (1819–1891)

    “There are three kinds of intelligence: one kind understands things for itself, the other appreciates what others can understand, the third understands neither for itself nor through others. This first kind is excellent, the second good, and the third kind useless.”
    —Niccolò Machiavelli (1469–1527)