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
East Islip, New York

... is spread out with 28.5% under the age of 18, 6.3% from 18 to 24, 32.3% from 25 to 44, 21.1% from 45 to 64, and 11.8% who are 65 years of age or older. The median age is 37 ...

This page was created in 37.2 ms