Stirling's Triangle for Subsets 

Stirling's Triangle for Subsets
15  25  10 
31  90  65  15 
63  301  350  140  21 
127  966  1701  1050  266  28 
255  3025  7770  6951  2646  462  36 

Stirling Number of the Second Kind

 The number of ways of partitioning a set of n elements into m non-empty sets (i.e., m blocks), also called a Stirling set number. For example, the set tex2html_wrap_inline12577 can be partitioned into three subsets in one way: tex2html_wrap_inline12579 ; into two subsets in three ways: tex2html_wrap_inline12581tex2html_wrap_inline12583, and tex2html_wrap_inline12585 ; and into one subset in one way: tex2html_wrap_inline12577 . The Stirling numbers of the second kind are denoted tex2html_wrap_inline11591tex2html_wrap_inline11573 , s(n, m), or tex2html_wrap_inline12188 , so the Stirling numbers of the second kind for 3 elements are


In general, the definition of the Stirling numbers of the second kind gives


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


or the generating functions





The following diagrams (Dickau) illustrate the definition of the Stirling numbers of the second kind tex2html_wrap_inline11573 for n=3 and 4.

Stirling numbers of the second kind obey the recurrence relations



for tex2html_wrap_inline11601 . An identity involving Stirling numbers of the second kind is


It turns out that f(1,n) can only have 0, 2, or 6 as a last digit (Riskin 1995)!


 Abramowitz, M. and Stegun, C. 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.

 Comtet, L. Advanced Combinatorics. Boston: D. 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.''

 Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1989.

 Knuth, D. E. ``Two Notes on Notation.'' Amer. Math. Monthly 99, 403-422, 1992.

 Riordan, J. An Introduction to Combinatorial Analysis. New York: Wiley, 1958.

 Riordan, J. Combinatorial Identities. New York: Wiley, 1968.

 Riskin, A. Problem 10231. Amer. Math. Monthly102, 175-176, 1995.

 Stanley, R. P. Enumerative Combinatorics, vol. 1. Monterey, CA: Wadsworth & Brooks/Cole, 1986.