Stirling's Triangle for Subsets 

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

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_inline12581 , tex2html_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_inline11591 , tex2html_wrap_inline11573 , s(n, m), or tex2html_wrap_inline12188 , so the Stirling numbers of the second kind for 3 elements are

displaymath17813

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

displaymath11603

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

displaymath12601

or the generating functions

displaymath13755

displaymath13757

and

displaymath12194

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

tex2html_wrap13332
Stirling numbers of the second kind obey the recurrence relations

displaymath11599

displaymath12198

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

displaymath11605

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

References

 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.'' http://forum.swarthmore.edu/advanced/robertd/stirling2.html.

 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.