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

<math>B_n=\sum_{k=1}^n S(n,k)</math>

is the nth Bell number. If we let

<math>(x)_n=x(x-1)(x-2)\cdots(x-n+1)</math>

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

<math>\sum_{k=1}^n S(n,k)(x)_k=x^n.</math>

(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

<math>E(X^n)=\sum_{k=1}^n S(n,k)\lambda^k.</math>

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[?].