## 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  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 denoted  , s(n, m), or  , 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

and

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

Stirling numbers of the second kind obey the recurrence relations

for  . 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)!

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.