## Encyclopedia > Stirling number

Article Content

# Stirling number

In combinatorics, Stirling numbers of the second kind S(n,k) (with a capital "S") count the number of equivalence relations having k equivalence classes defined on a set with n elements. The sum

$B_n=\sum_{k=1}^n S(n,k)$

is the nth Bell number. If we let

$(x)_n=x(x-1)(x-2)\cdots(x-n+1)$

(in particular, (x)0 = 1 because it is an empty product) be the falling factorial, we can characterize the Stirling numbers of the second kind by

$\sum_{k=1}^n S(n,k)(x)_k=x^n.$

(Confusingly, the notation that combinatorialists use for falling factorials coincides with the notation used in special functions for rising factorials; see Pochhammer symbol.) The Stirling numbers of the second kind enjoy the following relationship with the Poisson distribution: if X is a random variable with a Poisson distribution with expected value λ, then its nth moment is

$E(X^n)=\sum_{k=1}^n S(n,k)\lambda^k.$

In particular, the nth moment of the Poisson distribution with expected value 1 is precisely the number of partitions of a set of size n, i.e., it is the nth Bell number (this fact is "Dobinski's formula").

Unsigned Stirling numbers of the first kind s(n,k) (with a lower-case "s") count the number of permutations of n elements with k disjoint cycles[?].

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 1 E20 m ... from the Sun to the center of the Galaxy. 100,000 light years = 9.5 × 1020m -- diameter of the disc of the Galaxy. Distances longer than 1021 m See also: ...