![]() | ||
In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by
Contents
- Definition
- Notation
- Bell numbers
- Table of values
- Recurrence relation
- Lower and upper bounds
- Maximum
- Parity
- Simple identities
- Explicit formula
- Generating functions
- Asymptotic approximation
- Moments of the Poisson distribution
- Moments of fixed points of random permutations
- Rhyming schemes
- Associated Stirling numbers of the second kind
- Reduced Stirling numbers of the second kind
- References
Stirling numbers of the second kind are one of two kinds of Stirling numbers, the other kind being called Stirling numbers of the first kind (or Stirling cycle numbers). Mutually inverse (finite or infinite) triangular matrices can be formed from the Stirling numbers of each kind according to the parameters n, k.
Definition
The Stirling numbers of the second kind, written
as the only way to partition an n-element set into n parts is to put each element of the set into its own part, and the only way to partition a nonempty set into one part is to put all of the elements in the same part. They can be calculated using the following explicit formula:
Notation
Various notations have been used for Stirling numbers of the second kind. The brace notation
Bell numbers
The sum over the values for k of the Stirling numbers of the second kind, gives us
the nth Bell number, that is the total number of partitions of a set with n members.
If we let
(in particular, (x)0 = 1 because it is an empty product) be the falling factorial, we can characterize the Stirling numbers of the second kind by
Analogously, the ordered Bell numbers can be computed from the Stirling numbers of the second kind as
Table of values
Below is a triangular array of values for the Stirling numbers of the second kind (sequence A008277 in the OEIS):
As with the binomial coefficients, this table could be extended to k > n, but those entries would all be 0.
Recurrence relation
Stirling numbers of the second kind obey the recurrence relation
for k > 0 with initial conditions
for n > 0.
For instance, the number 25 in column k=3 and row n=5 is given by 25=7+(3×6), where 7 is the number above and to the left of 25, 6 is the number above 25 and 3 is the column containing the 6.
To understand this recurrence, observe that a partition of the n+1 objects into k nonempty subsets either contains the n+1-th object as a singleton or it does not. The number of ways that the singleton is one of the subsets is given by
since we must partition the remaining
since we partition all objects other than the n+1-th into k subsets, and then we are left with k choices for inserting object n+1. Summing these two values gives the desired result.
Some more recurrences are as follows:
Lower and upper bounds
If
where
and
Maximum
For fixed
When
and the maximum value of the Stirling number of second kind is
Parity
The parity of a Stirling number of the second kind is equal to the parity of a related binomial coefficient:
This relation is specified by mapping n and k coordinates onto the Sierpiński triangle.
More directly, let two sets contain positions of 1's in binary representations of results of respective expressions:
One can mimic a bitwise AND operation by intersecting these two sets:
to obtain the parity of a Stirling number of the second kind in O(1) time. In pseudocode:
where
Simple identities
Some simple identities include
This is because dividing n elements into n − 1 sets necessarily means dividing it into one set of size 2 and n − 2 sets of size 1. Therefore we need only pick those two elements;
and
To see this, first note that there are 2 n ordered pairs of complementary subsets A and B. In one case, A is empty, and in another B is empty, so 2 n − 2 ordered pairs of subsets remain. Finally, since we want unordered pairs rather than ordered pairs we divide this last number by 2, giving the result above.
Another explicit expansion of the recurrence-relation gives identities in the spirit of the above example.
Explicit formula
The Stirling numbers of the second kind are given by the explicit formula:
This formula is a special case of the kth forward difference of the monomial
Because the Bernoulli polynomials may be written in terms of these forward differences, one immediately obtains a relation in the Bernoulli numbers:
Generating functions
For a fixed integer n, generating functions for the Stirling numbers of the second kind
where
For a fixed integer k, the Stirling numbers of the second kind
and an exponential generating function:
Note that
A mixed bivariate generating function (exponential in x and ordinary in y) for the Stirling numbers of the second kind is
Asymptotic approximation
For fixed value of
On the other side, for
Uniformly valid approximation also exist
where
Moments of the Poisson distribution
If X is a random variable with a Poisson distribution with expected value λ, then its nth moment is
In particular, the nth moment of the Poisson distribution with expected value 1 is precisely the number of partitions of a set of size n, i.e., it is the nth Bell number (this fact is Dobinski's formula).
Moments of fixed points of random permutations
Let the random variable X be the number of fixed points of a uniformly distributed random permutation of a finite set of size m. Then the nth moment of X is
Note: The upper bound of summation is m, not n.
In other words, the nth moment of this probability distribution is the number of partitions of a set of size n into no more than m parts. This is proved in the article on random permutation statistics, although the notation is a bit different.
Rhyming schemes
The Stirling numbers of the second kind can represent the total number of rhyme schemes for a poem of n lines.
Associated Stirling numbers of the second kind
An r-associated Stirling number of the second kind is the number of ways to partition a set of n objects into k subsets, with each subset containing at least r elements. It is denoted by
The 2-associated numbers (sequence A008299 in the OEIS) appear elsewhere as "Ward numbers" and as the magnitudes of the coefficients of Mahler polynomials.
Reduced Stirling numbers of the second kind
Denote the n objects to partition by the integers 1, 2, ..., n. Define the reduced Stirling numbers of the second kind, denoted
(hence the name "reduced"). Observe (both by definition and by the reduction formula), that