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.