TOPICS
Search

Stirling Number of the Second Kind

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The number of ways of partitioning a set of n elements into m nonempty sets (i.e., m set blocks), also called a Stirling set number. For example, the set {1,2,3} can be partitioned into three subsets in one way: {{1},{2},{3}}; into two subsets in three ways: {{1,2},{3}}, {{1,3},{2}}, and {{1},{2,3}}; and into one subset in one way: {{1,2,3}}.

The Stirling numbers of the second kind are variously denoted S(n,m) (Riordan 1980, Roman 1984), S_n^((m)) (Fort 1948; Abramowitz and Stegun 1972, p. 822), S_n^m (Jordan 1965), s_n^((m)), S_2(n,m), or Knuth's notation {n; m} (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 S_n^((m)).

The Stirling numbers of the second kind for three elements are

S(3,1)=1
(1)
S(3,2)=3
(2)
S(3,3)=1.
(3)

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

S(n,1)=S(n,n)=1.
(4)

Other special cases include

S(n,0)=delta_(n0)
(5)
S(n,2)=2^(n-1)-1
(6)
S(n,3)=1/6(3^n-3·2^n+3)
(7)
S(n,n-1)=(n; 2).
(8)

The triangle of Stirling numbers of the second kind is

1 1 1 1 3 1 1 7 6 1 1 15 25 10 1 1 31 90 65 15 1
(9)

(OEIS A008277), the nth row of which corresponds to the coefficients of the Bell polynomial phi_n(x).

The Stirling numbers of the second kind can be computed from the sum

S(n,k)=1/(k!)sum_(i=0)^k(-1)^i(k; i)(k-i)^n,
(10)

with (n; k) a binomial coefficient, or the generating functions

x^n=sum_(m=0)^(n)S(n,m)(x)_m
(11)
=sum_(m=0)^(n)S(n,m)x(x-1)...(x-m+1),
(12)

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

sum_(n=k)^inftyS(n,k)(x^n)/(n!)=1/(k!)(e^x-1)^k,
(13)

and

sum_(n=1)^(infty)S(n,k)x^n=sum_(n=k)^(infty)S(n,k)x^n
(14)
=(x^k)/((1-x)(1-2x)...(1-kx))
(15)
=((-1)^k)/(((x-1)/x)_k)
(16)

for z<1/m (Abramowitz and Stegun 1972, p. 824; Stanley 1997, p. 57), where (x)_m is a Pochhammer symbol. Another generating function is given by

sum_(k=1)^nS(n,k)(k-1)!z^k=(-1)^nLi_(1-n)(1+1/z)
(17)

for n>=2, where Li_n(z) is the polylogarithm.

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

B_n(x)=sum_(k=0)^nx^kS(n,k)
(18)

where B_n(x) is a Bell polynomial.

StirlingNumberSecondKind

The above diagrams (Dickau) illustrate the definition of the Stirling numbers of the second kind S(n,m) for n=3 and 4. Stirling numbers of the second kind obey the recurrence relations

S(n,k)=S(n-1,k-1)+kS(n-1,k)
(19)
S(n,k)=sum_(m=k)^(n)k^(n-m)S(m-1,k-1).
(20)

The Stirling numbers of the first kind s(n,m) are connected with the Stirling numbers of the second kind S(n,m). For example, the matrices (s)_(i,j) and (S)_(i,j) are inverses of each other, where (A)_(ij) denotes the matrix with (i,j)th entry aAi,j) for i,j=1, ..., n (G. Helms, pers. comm., Apr. 28, 2006).

Other formulas include

s(n,i)=sum_(k=i)^nsum_(j=0)^ks(n,k)s(k,j)S(j,i)
(21)
S(n,i)=sum_(k=i)^nsum_(j=0)^kS(n,k)S(k,j)s(j,i)
(22)

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

S(n,m)=sum_(k=0)^(n-m)(-1)^k(k+n-1; k+n-m)(2n-m; n-k-m)s(k-m+n,k)
(23)
s(n,m)=sum_(k=0)^(n-m)(-1)^k(k+n-1; k+n-m)(2n-m; n-k-m)S(k-m+n,k)
(24)
sum_(l=0)^(max(k,j)+1)s(l,j)S(k,1)=delta_(jk)
(25)
sum_(l=0)^(max(k,j)+1)s(k,l)S(l,j)=delta_(jm).
(26)

Identities involving Stirling numbers of the second kind are given by

sum_(m=1)^n(-1)^m(m-1)!S(n,m)=0
(27)
sum_(k=0)^nk!(m+1; k+1)S(n,k)=H_(m,-n),
(28)

where H_(n,r) is a generalized harmonic number, and

f(m,n)=sum_(k=1)^(infty)k^n(m/(m+1))^k
(29)
=(m+1)sum_(k=1)^(n)k!S(n,k)m^k.
(30)

The sequence f(1,n) 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

sum_(k=0)^inftyk^n[k+1-(Gamma(k+2,1))/(Gamma(k+1))]=sum_(k=0)^n(S(n,k))/(k+2)
(31)

for n=0, 1, ..., where Gamma(a,x) is an incomplete gamma function, Gamma(x) is a gamma function, and k^n is taken to be 1 for k,n=0.

Stirling numbers of the second kind also occur in identities involving the differential operator theta=zd/dz.

See also

Bell Number, Bell Polynomial, Combination Lock, Complementary Bell Number, Differential Operator, Lengyel's Constant, Minimal Cover, Poisson Distribution, Stirling Number of the First Kind, Stirling Polynomial, Stirling Transform

Related Wolfram sites

http://functions.wolfram.com/IntegerFunctions/StirlingS2/

Explore with Wolfram|Alpha

References

Abramowitz, M. and Stegun, I. A. (Eds.). "Stirling Numbers of the Second Kind." §24.1.4 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, pp. 824-825, 1972.Butzer, P. L. and Hauss, M. "Stirling Functions of the First and Second Kinds; Some New Applications." Israel Mathematical Conference Proceedings: Approximation, Interpolation, and Summability, in Honor of Amnon Jakimovski on his Sixty-Fifth Birthday (Ed. S. Baron and D. Leviatan). Ramat Gan, Israel: IMCP, pp. 89-108, 1991.Carlitz, L. "Note on Nörlund's [sic] Polynomial B_n^((z))." Proc. Amer. Math. Soc. 11, 452-455, 1960.Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, 1974.Conway, J. H. and Guy, R. K. In The Book of Numbers. New York: Springer-Verlag, pp. 91-92, 1996.Dickau, R. M. "Stirling Numbers of the Second Kind." http://mathforum.org/advanced/robertd/stirling2.html.Dickau, R. "Visualizing Combinatorial Enumeration." Mathematica in Educ. Res. 8, 11-18, 1999.Fort, T. Finite Differences and Difference Equations in the Real Domain. Oxford, England: Clarendon Press, 1948.Gould, H. W. "Stirling Number Representation Problems." Proc. Amer. Math. Soc. 11, 447-451, 1960.Graham, R. L.; Knuth, D. E.; and Patashnik, O. "Stirling Numbers." §6.1 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, pp. 257-267, 1994.Jordan, C. Calculus of Finite Differences, 3rd ed. New York: Chelsea, 1965.Knuth, D. E. "Two Notes on Notation." Amer. Math. Monthly 99, 403-422, 1992.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.Konhauser, J. D. E.; Velleman, D.; and Wagon, S. Which Way Did the Bicycle Go? And Other Intriguing Mathematical Mysteries. Washington, DC: Math. Assoc. Amer., p. 174, 1996.Riordan, J. Combinatorial Identities. New York: Wiley, 1979.Riordan, J. An Introduction to Combinatorial Analysis. New York: Wiley, 1980.Riskin, A. "Problem 10231." Amer. Math. Monthly 102, 175-176, 1995.Roman, S. The Umbral Calculus. New York: Academic Press, pp. 59-63, 1984.Sloane, N. J. A. Sequences A000629 and A008277 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, 1997.Stirling, J. Methodus differentialis, sive tractatus de summation et interpolation serierum infinitarium. London, 1730. English translation by Holliday, J. The Differential Method: A Treatise of the Summation and Interpolation of Infinite Series. 1749.Young, P. T. "Congruences for Bernoulli, Euler, and Stirling Numbers." J. Number Th. 78, 204-227, 1999.

Referenced on Wolfram|Alpha

Stirling Number of the Second Kind

Cite this as:

Weisstein, Eric W. "Stirling Number of the Second Kind." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html

Subject classifications