Stirling Number of the Second Kind

The number of ways of partitioning a set of $n$ elements into $m$ nonempty Sets (i.e., $m$ 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 denoted $s_n^{(m)}$, $S_2(n,m)$, $S(n, m)$, or $\left\{\matrix{n\cr m\cr}\right\}$, so 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)

The triangle of Stirling numbers of the second kind is

$1$
$1 \quad 1$
$1 \quad 3 \quad 1$
$1 \quad 7 \quad 6 \quad 1$
$1 \quad 15 \quad 25 \quad 10 \quad 1$
$1 \quad 31 \quad 90 \quad 65 \quad 15 \quad 1$

(Sloane's A008277).

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

$$S(n,k)={1\over k!}\sum_{i=0}^{k-1} (-1)^i{k\choose i}(k-i)^n,$$ (5)

with ${n\choose k}$ a Binomial Coefficient, or the Generating Functions

$$x^n = \sum_{m=0}^n S(n,m) x(x-1)\cdots(x-m+1),$$ (6)

$$\sum_{n\geq k} S(n,k) {x^n\over n!}={1\over k!}(e^x-1)^k,$$ (7)

and

$${1\over(1-x)(1-2x)\cdots(1-kx)}=\sum_{n=1}^k S(n,k) x^n.$$ (8)

The following 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).$$ (9)

An identity involving Stirling numbers of the second kind is

$$f(m, n)\equiv \sum_{k=1}^\infty k^n\left({m\over m+1}\right)^l = (m+1)\sum_{k=1}^m k! S(n,k)m^k.$$ (10)

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

See also Bell Number, Combination Lock, Lengyel's Constant, Minimal Cover, Stirling Number of the First Kind

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: The Art of Finite and Infinite Expansions, rev. enl. ed. Boston, MA: 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, 1994.

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

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

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

Riskin, A. ``Problem 10231.'' Amer. Math. Monthly 102, 175-176, 1995.

Sloane, N. J. A. Sequence A008277 in ``The On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.

Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, 1997.