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

Stirling Numbers of The Second Kind

These numbers count the number of partitions of into k nonempty subsets. First consider the total number of partitions, i.e. Bn where

B_n = \sum_{k=1}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\} \mbox{ and } B_0 = 1,

i.e. the Bell numbers. The Symbolic combinatorics#The Flajolet–Sedgewick fundamental theorem applies (labelled case). The set of partitions into non-empty subsets is given by ("set of non-empty sets of singletons")

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

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

Differentiate to obtain

\frac{d}{dz} B(z) = \exp \left(\exp z - 1\right) \exp z = B(z) \exp z,

which implies that

by convolution of exponential generating functions and because differentiating an EGF drops the first coefficient and shifts Bn+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, giving

Translating to generating functions, we obtain

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

\left\{\begin{matrix} n \\ k \end{matrix}\right\} = n! B(z, u) = n! \frac{(\exp z - 1)^k}{k!}

or

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.

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)

    “The only phenomenon with which writing has always been concomitant is the creation of cities and empires, that is the integration of large numbers of individuals into a political system, and their grading into castes or classes.... It seems to have favored the exploitation of human beings rather than their enlightenment.”
    —Claude Lévi-Strauss (b. 1908)

    “The television screen, so unlike the movie screen, sharply reduced human beings, revealed them as small, trivial, flat, in two banal dimensions, drained of color. Wasn’t there something reassuring about it!—that human beings were in fact merely images of a kind registered in one another’s eyes and brains, phenomena composed of microscopic flickering dots like atoms. They were atoms—nothing more. A quick switch of the dial and they disappeared and who could lament the loss?”
    —Joyce Carol Oates (b. 1938)