Bell numbers

In combinatorial mathematics, the nth Bell number, named in honor of Eric Temple Bell, is the number of partitions of a set with n members. The sequence of Bell numbers begins as follows Template:OEIS:

<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>

Contents

1 Partitions of a set 2 Another view of Bell numbers 3 Properties of Bell numbers 4 An visual way of calculating Bell numbers 5 See also 6 External links

Partitions of a set

In general, B_n 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, B₃ = 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}}

B₀ 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.

Another view of Bell numbers

Bell numbers can also be viewed as the number of distinct possible ways of putting n labelled balls in to one or more anonymous boxes. For example, let us suppose n is 3. We have three balls, which we will label a, b, and c, and three boxes. If the boxes can not be distinguished from each other, there are five ways of putting the balls in the boxes:

• Each ball goes in to its own box.
• All three balls go in to one box. Since the boxes are anonymous, this is only considered one combination.
• a goes in to one box; b and c go in to another box.
• b goes in to one box; a and c go in to another box.
• c goes in to one box; a and b go in to another box.

Properties of Bell numbers

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!}=<math> 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

<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.

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

<math>\sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.<math>

An visual way of calculating Bell numbers

This sequence can be easily calculated by the following steps:

1. Start with the number one. Put this on a row by itself.
2. Start a new row with the rightmost element from the previous row as the leftmost number
3. Determine the numbers not on the left column by taking the sum of the number to the left and the number above the number to the left (the number diagonally up and left of the number we are calculating)
4. Repeat step three until there is a new row with one more number than the previous row
5. The number on the left hand side of a given row is the Bell number for that row.

For example, the first row is made by placing one by itself. The next (second) row is made by taking the rightmost number from the previous row (1), and placing it on a new row. We now have a structure like this:

 1
 1  x

The value x here is determined by adding the number to the left of x (one) and the number above the number to the left of x (also one).

 1
 1  2
 y

The value y is determined by copying over the number from the right of the previous row. Since the number on the right hand side of the previous row has a value of 2, y is given a value of two.

 1
 1  2
 2  3  x

Again, since x is not the leftmost element of a given row, its value is determined by taking the sum of the number to x's left (three) and the number above the number to x's left (two). The sum is five.

Here is the first five rows of this triangle:

 1
 1  2
 2  3  5
 5  7 10 15
15 20 27 37 52

The fifth row is calculated thusly:

• Take 15 from the previous row
• 15 + 5 = 20
• 20 + 7 = 27
• 27 + 10 = 37
• 37 + 15 = 52

See also

• Bell polynomials

External links

• Diagrams of Bell numbers (http://mathforum.org/advanced/robertd/bell.html)
• Using the Bell Triangle to calculate Bell numbers (http://www.pballew.net/Bellno.html)fr:Nombre de Bell

zh:贝尔数