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

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



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
Kings Park, New York

... out with 25.2% under the age of 18, 5.7% from 18 to 24, 31.9% from 25 to 44, 23.3% from 45 to 64, and 13.9% who are 65 years of age or older. The median age is 38 years. ...

 
 
 
This page was created in 33.4 ms