Stirling numbers of the second kind
In mathematics, particularly in combinatorics, a Stirling number of the second kind is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions.
Stirling numbers of the second kind is one of two kinds of Stirling numbers, the other kind being called Stirling numbers of the first kind. Mutually inverse (finite or infinite) triangular matrices can be formed by arranging the Stirling numbers of the first respectively second kind according to the parameters n, k.
The Stirling numbers of the second kind count the number of ways to partition a set of n labelled objects into k nonempty unlabelled subsets. Equivalently, they count the number of different equivalence relations with precisely k equivalence classes that can be defined on an n element set. Obviously,
They can be calculated using the following explicit formula:
Various notations have been used for Stirling numbers of the second kind. The brace notation was used by Imanuel Marx and Antonio Salmeri in 1962 for variants of these numbers. This led Knuth to use it, as shown here, in the first volume of The Art of Computer Programming (1968). However, according to the third edition of The Art of Computer Programming, this notation was also used earlier by Jovan Karamata in 1935. The notation S(n,k) was used by Richard Stanley in his book Enumerative Combinatorics.
Bell numbers 
The sum over the values for k of the Stirling numbers of the second kind, gives us
If we let
Table of values 
|n \ k||0||1||2||3||4||5||6||7||8||9||10|
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 objects into the available k-1 subsets. In the other case the n+1-th object belongs to a subset containing other objects. The number of ways is given by
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 and , then
For fixed , has a single maximum. That is, there is a such that
When is large
and the maximum value of the Stirling number of second kind at is
This relation is specified by mapping n and k coordinates onto the Sierpiński triangle.
Or directly, let two sets contain positions of 1's in binary representations of results of respective expressions:
then mimic a bitwise AND operation by intersecting these two sets:
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;
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 expanding 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:
Generating function 
A generating function for the Stirling numbers of the second kind is given by
A rational generating function is given by
Two exponential generating functions are given by
Asymptotic approximation 
For fixed value of the asymptotic value of the Stirling numbers of the second kind is given by
Moments of the Poisson distribution 
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 
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. gives the number of possible rhyming schemes for n lines using k unique rhyming syllables. As an example, for a poem of 3 lines, there is 1 rhyme scheme using just one rhyme (aaa), 3 rhyme schemes using two rhymes (aab, aba, abb), and 1 rhyme scheme using three rhymes (abc).
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 and obeys the recurrence relation
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 , to be the number of ways to partition the integers 1, 2, ..., n into k nonempty subsets such that all elements in each subset have pairwise distance at least d. That is, for any integers i and j in a given subset, it is required that . It has been shown that these numbers satisfy
(hence the name "reduced"). Observe (both by definition and by the reduction formula), that , the familiar Stirling numbers of the second kind.
See also 
- Bell number – the number of partitions of a set with n members
- Stirling numbers of the first kind
- Partition related number triangles
- Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1988) Concrete Mathematics, Addison–Wesley, Reading MA. ISBN 0-201-14236-8, p. 244.
- Sharp, Henry (1968), "Cardinality of finite topologies", J. Combinatorial Theory 5: 82–86, doi:10.1016/S0021-9800(68)80031-6, MR0226578
- Transformation of Series by a Variant of Stirling's Numbers, Imanuel Marx, The American Mathematical Monthly 69, #6 (June–July 1962), pp. 530–532, JSTOR 2311194.
- Antonio Salmeri, Introduzione alla teoria dei coefficienti fattoriali, Giornale di Matematiche di Battaglini 90 (1962), pp. 44–54.
- p. 410–412, Two Notes on Notation, Donald E. Knuth, The American Mathematical Monthly 99, #5 (May 1992), pp. 403–422, JSTOR 2325085.
- Donald E. Knuth, Fundamental Algorithms, Reading, Mass.: Addison–Wesley, 1968.
- p. 66, Donald E. Knuth, Fundamental Algorithms, 3rd ed., Reading, Mass.: Addison–Wesley, 1997.
- Jovan Karamata, Théorèmes sur la sommabilité exponentielle et d'autres sommabilités s'y rattachant, Mathematica (Cluj) 9 (1935), pp, 164–178.
- Confusingly, the notation that combinatorialists use for falling factorials coincides with the notation used in special functions for rising factorials; see Pochhammer symbol.
- Sprugnoli, Renzo (1994), "Riordan arrays and combinatorial sums", Discrete Mathematics 132 (1-3): 267–290, doi:10.1016/0012-365X(92)00570-H, MR 1297386.
- B.C. Rennie, A.J. Dobson. "On Stirling Numbers of the Second Kind"
- L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222.
- A. Mohr and T.D. Porter, Applications of Chromatic Polynomials Involving Stirling Numbers, Journal of Combinatorial Mathematics and Combinatorial Computing 70 (2009), 57–64.
- Stirling numbers of the second kind, S(n,k), PlanetMath.org..
- Weisstein, Eric W., "Stirling Number of the Second Kind", MathWorld.
- Calculator for Stirling Numbers of the Second Kind
- Set Partitions: Stirling Numbers
- Jack van der Elsen, Black and white transformations, Maastricht 2005, ISBN 90-423-0263-1