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

			(1)
			(2)
			(3)

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

(4)

Other special cases include

			(5)
			(6)
			(7)
			(8)

The triangle of Stirling numbers of the second kind is

(9)

(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

(10)

with a binomial coefficient, or the generating functions

			(11)
			(12)

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

(13)

and

			(14)
			(15)
			(16)

for (Abramowitz and Stegun 1972, p. 824; Stanley 1997, p. 57), where is a Pochhammer symbol. Another generating function is given by

(17)

for , where is the polylogarithm.

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

(18)

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

			(19)
			(20)

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

(21)

(22)

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

(23)

(24)

(25)

(26)

Identities involving Stirling numbers of the second kind are given by

(27)

(28)

where is a generalized harmonic number, and

			(29)
			(30)

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

(31)

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 .

Wolfram Web Resources