Stirling Number of the Second Kind
The number of ways of partitioning a set of elements into nonempty sets (i.e., set blocks), also called a Stirling set number. For example, the set can be partitioned into three subsets in one way: ; into two subsets in three ways: , , and ; and into one subset in one way: .
The Stirling numbers of the second kind are variously denoted (Riordan 1980, Roman 1984), (Fort 1948; Abramowitz and Stegun 1972, p. 822), (Jordan 1965), , , or Knuth's notation (Graham et al. 1994; Knuth 1997, p. 65). Abramowitz and Stegun (1972, p. 822) summarize the various notational conventions, which can be a bit confusing. The Stirling numbers of the second kind are implemented in the Wolfram Language as StirlingS2[n, m], and denoted .
The Stirling numbers of the second kind for three elements are
Since a set of elements can only be partitioned in a single way into 1 or subsets,
Other special cases include
The triangle of Stirling numbers of the second kind is
(OEIS A008277), the th row of which corresponds to the coefficients of the Bell polynomial .
The Stirling numbers of the second kind can be computed from the sum
with a binomial coefficient, or the generating functions
where is the falling factorial (Roman 1984, pp. 60 and 101),
for (Abramowitz and Stegun 1972, p. 824; Stanley 1997, p. 57), where is a Pochhammer symbol. Another generating function is given by
for , where is the polylogarithm.
Stirling numbers of the second kind are intimately connected with the Poissondistribution through Dobiński's formula
where is a Bell polynomial.
The above diagrams (Dickau) illustrate the definition of the Stirling numbers of the second kind for and 4. Stirling numbers of the second kind obey the recurrence relations
The Stirling numbers of the first kind are connected with the Stirling numbers of the second kind . For example, the matrices and are inverses of each other, where denotes the matrix with th entry for , ..., (G. Helms, pers. comm., Apr. 28, 2006).
Other formulas include
(Roman 1984, p. 67), as well as
Identities involving Stirling numbers of the second kind are given by
where is a generalized harmonic number, and
The sequence is given by 2, 6, 26, 150, 1082, 9366, 94586, 1091670, ... (OEIS A000629; Konhauser et al. 1996, p. 174), and can have only 0, 2, or 6 as a last digit (Riskin 1995). An additional curious identity due to K. A. Penson (pers. comm., April 10, 2002) is given by
for , 1, ..., where is an incomplete gamma function, is a gamma function, and is taken to be 1 for .
Stirling numbers of the second kind also occur in identities involving the differential operator .