Encyclopedia > Bell numbers

  Article Content

Bell numbers

The Bell numbers, named in honor of Eric Temple Bell, are a sequence of integers arising in combinatorics that begins thus:
<math>B_0=1,\quad B_1=1,\quad B_2=2,\quad B_3=5,\quad B_4=15,\quad B_5=52,\quad B_6=203,\quad\dots</math>
In general, Bn is the number of partitions of a set of size n. (B0 is 1 because there is exactly one partition of the empty set. A partition of a set S is by definition a set of nonempty sets whose union is S. Every member of the empty set is a nonempty set (that is vacuously true), and their union is the empty set. Therefore, the empty set is the only partition of itself.)

The Bell numbers satisfy this recursion formula:

<math>B_{n+1}=\sum_{k=0}^{n}{{n \choose k}B_k}.</math>
They also satisfy "Dobinski's formula":
<math>B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}={\rm\ the\ }n{\rm th\ moment\ of\ a\ Poisson\ distribution\ with\ expected\ value\ 1}.</math>
And they satisfy "Touchard's congruence": If p is any prime number then
<math>B_{p+n}\equiv B_n+B_{n+1}\ (\operatorname{mod}\ p).</math>

Each Bell number is a sum of "Stirling numbers of the second kind"

<math>B_n=\sum_{k=1}^n S(n,k).</math>
The Stirling number S(n, k) is the number of ways to partition a set of cardinality n into exactly k nonempty subsets.



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
KANU

... new parties had formed, and multiparty elections were held in December 1992. President Moi was reelected for another 5-year term. Opposition parties won about 45% of the ...

 
 
 
This page was created in 82.5 ms