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 ye poets of the age,
    All ye witlings of the stage,
    Learn your jingles to reform,
    Crop your numbers to conform.
    Let your little verses flow
    Gently, sweetly, row by row;
    Let the verse the subject fit,
    Little subject, little wit.
    Namby-Pamby is your guide,
    Albion’s joy, Hibernia’s pride.”
    —Henry Carey (1693?–1743)

    “Being good in business is the most fascinating kind of art.... Making money is art and working is art and good business is the best art.”
    —Andy Warhol (1928–1987)