Stirling number
In combinatorics, 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.
Stirling numbers of the first kind (without the qualifiying adjective unsigned) are the coefficients in the expansion
where (x)n is the rising factorial
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:
-
