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 |
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.
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.