(Redirected from
Bell number)
The Bell numbers, named in honor of Eric Temple Bell, are a sequence of integers arising in combinatorics that begins thus :
In general, Bn is the number of partitions of a set of size n. A partition of a set S is defined as a set of nonempty, pairwise disjoint subsets of S whose union is S. For example, B3 = 5 because the 3-element set {a, b, c} can be partitioned in 5 distinct ways:
- {{a}, {b}, {c}}
- {{a}, {b, c}}
- {{b}, {a, c}}
- {{c}, {a, b}}
- {{a, b, c}}
B0 is 1 because there is exactly one partition of the empty set. 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:
They also satisfy "Dobinski's formula":
the n-th moment of a Poisson distribution with expected value 1.
And they satisfy "Touchard's congruence": If p is any prime number then
Each Bell number is a sum of "Stirling numbers of the second kind"
The Stirling number S(n, k) is the number of ways to partition a set of cardinality n into exactly k nonempty subsets.
The n-th Bell number is also the sum of the coefficients in the polynomial that expresses the nth moment of any probability distribution as a function of the first n cumulants; this way of enumerating partitions is not as coarse as that given by the Stirling numbers.
The exponential generating function of the Bell numbers is
See also
Last updated: 08-22-2005 02:02:35
