Stirling Number of the Second Kind

A Stirling number of the second kind is the number of ways of partitioning a set of elements into nonempty sets (i.e., set blocks), where and are nonnegative integers. It is also called a Stirling set number. The empty set gives , and for . 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: .

Equivalently, counts the ways of distributing distinct balls into identical nonempty boxes, one of the cases in the twelvefold 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 .

For , a set of elements can only be partitioned in a single way into 1 or subsets,

(1)

Other special cases include (with in the last three formulas)

			(2)
			(3)
			(4)
			(5)

The triangle of Stirling numbers of the second kind is

(6)

(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

(7)

with a binomial coefficient, or the generating functions

			(8)
			(9)

where is the falling factorial (Roman 1984, pp. 60 and 101),

(10)

and

			(11)
			(12)
			(13)

for and (Abramowitz and Stegun 1972, p. 824; Stanley 1997, p. 57), where denotes the rising factorial (Pochhammer symbol) in this formula, and the last expression is extended to by continuity. Another generating function is given by

(14)

for and , with extension to by continuity, where is the polylogarithm.

Stirling numbers of the second kind are intimately connected with the Poisson distribution through Dobiński's formula

(15)

where is a Bell polynomial.

The above diagrams (Dickau) illustrate the definition of the Stirling numbers of the second kind for and 4. For and , Stirling numbers of the second kind obey the recurrence relations

			(16)
			(17)

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

(18)

(19)

(Roman 1984, p. 67), as well as

(20)

(21)

(22)

(23)

Identities involving Stirling numbers of the second kind are given by

(24)

for .

(25)

for integers and , where is a generalized harmonic number, and

			(26)
			(27)

The identity holds for integers and real numbers . The sequence for 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

(28)

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 .