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
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
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:
or
which simplifies to
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)
“Mo Williams: Some people peddle apples, lamb chops, lumber. I peddle information. Skip aint sorry; he understands. We live in a different kind of world. Oh, once in a while he gets a little hot under the collar if I sell him short.
Candy: But you wouldnt sell him to a Commie!
Mo Williams: What do you think I am, an informer?!”
—Samuel Fuller (b. 1911)