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
Shinnecock Hills, New York

... the age of 18 living with them, 52.8% are married couples living together, 6.8% have a female householder with no husband present, and 37.6% are non-families. 27.7% of all ...

This page was created in 24 ms