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, or equivalently, the number of equivalence relations on it. Starting with B₀ = B₁ = 1, the first few Bell numbers are :

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975

(See also breakdown by number of subsets/equivalence classes.)

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:

e^{\lambda \left( n \right) - n - 1}

Where $\backslash lambda\; \backslash left(\; n\; \backslash right)$ definied by

$\backslash lambda\; \backslash left(\; n\; \backslash right)\backslash ln\; \backslash lambda\; \backslash left(\; n\; \backslash right)\; =\; n$

(Lovász, 1993)

Triangle scheme for calculating Bell numbers

The Bell numbers can easily be calculated by creating the so-called Bell triangle, also called Aitken's array or the Peirce triangle:

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

The number in the nth row and kth column is the number of partitions of {1, ..., n} such that n is not together in one class with any of the elements k, k + 1, ..., n − 1. For example, there are 7 partitions of {1, ..., 4} such that 4 is not together in one class with either of the elements 2, 3, and there are 10 partitions of {1, ..., 4} such that 4 is not together in one class with element 3. The difference is due to 3 partitions of {1, ..., 4} such that 4 is together in one class with element 2, but not with element 3. This corresponds to the fact that there are 3 partitions of {1, ..., 3} such that 3 is not together in one class with element 2: for counting partitions two elements which are always in one class can be treated as just one element. The 3 appears in the previous row of the table.

Using this way of calculating the following JavaScript shows the first 219 Bell numbers: function write_bell ( hBound ) { // writes Bell-0 , ... , Bell-hBound var value = 123.456 , 1 // value = unimportant, value [1 = 1 for ( var rowNr = 0 ; rowNr <= hBound ; rowNr ++ ) { value = value [1 for ( var colNr = rowNr - 1 ; colNr >= 1 ; colNr-- ) value += value [colNr+1 document.write ( 'Bell-' + rowNr + ' = ' + value ^* + '<br>' ) } } write_bell ( 218 )

References

• Gian-Carlo Rota, "The Number of Partitions of a Set", American Mathematical Monthly, volume 71, number 5, pages 498—504, May 1964.

See also

• Bell polynomials
• Bell prime

External links

• Diagrams of Bell numbers.
• Using the Bell Triangle to calculate Bell numbers.

Integer sequences

Bellsche Zahl | Nombre de Bell | Liczba Bella | 贝尔数