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
is the
nth
Bell number.
If we let
(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
(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
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").
In recent years, the Stirling numbers of the second kind have often been denoted in a way introduced by Donald Knuth:
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.