Bell number

In combinatorics, the nth Bell number, named after 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 B0 = B1 = 1, the first few Bell numbers are:

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, … (sequence A000110 in OEIS).

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

Partitions of a set
The 52 partitions of a set with 5 elements

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.

Note that, as suggested by the set notation above, we consider neither the order of the partitions nor the order of elements within each partition. This means the following partitionings are all considered identical:

{ {b}, {a, c} }
{ {a, c}, {b} }
{ {b}, {c, a} }
{ {c, a}, {b} }.

Properties of Bell numbers

The Bell numbers satisfy this recursion formula:

\( B_{n+1}=\sum_{k=0}^{n}{{n \choose k}B_k}. \)

They also satisfy "Dobinski's formula":

\( B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!} \)

= the nth moment of a Poisson distribution with expected value 1.

And they satisfy "Touchard's congruence": If p is any prime number then

\( B_{p+n}\equiv B_n+B_{n+1}\ (\operatorname{mod}\ p). \)

or, generalizing

\( B_{p^m+n}\equiv mB_n+B_{n+1}\ (\operatorname{mod}\ p). \)

Each Bell number is a sum of Stirling numbers of the second kind

\( B_n=\sum_{k=0}^n \left\{{n\atop k}\right\} =\sum_{k=0}^n \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j} j^n \)

The Stirling number \( \left\{{n\atop k}\right\} \)is the number of ways to partition a set of cardinality n into exactly k nonempty subsets.

More generally, the Bell numbers satisfy the following recurrence[1]:

\( B_{n+m} = \sum_{k=0}^n \sum_{j=0}^m \left\{{m\atop j}\right\} {n \choose k} j^{n-k} B_k. \)

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

\( \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}. \)

Asymptotic limit and bounds

Several asymptotic formulae for the Bell numbers are known. One such is

\( B_n \sim \frac{1}{{\sqrt n }}\left[ {\lambda \left( n \right)} \right]^{n + \frac{1}{2}} e^{\lambda \left( n \right) - n - 1}. \)

Here

\( \lambda(n) = e^{W(n)}= \frac{n}{W(n)},\, \)

where W is the Lambert W function.

(Lovász, 1993)

In (Berend, D. and Tassa, T., 2010), the following bounds were established:

\( B_n < \left( \frac{0.792 n}{\ln( n+1)} \right)^n ~; \)

moreover, if \( \varepsilon>0 \) then for all \(n > n_0(\varepsilon) \),

\( B_n < \left( \frac{e^{-0.6 + \varepsilon} n}{\ln(n+1)}\right)^n \)

where \( ~n_0(\varepsilon) = \max\left\{e^4,d^{-1}(\varepsilon) \right\}~ and ~d(x):= \ln \ln (x+1) - \ln \ln x + \frac{1+e^{-1}}{\ln x}\,. \)
Triangle scheme for calculating Bell numbers
The triangular array whose right-hand diagonal sequence consists of Bell numbers

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

Start with the number one. Put this on a row by itself.
Start a new row with the rightmost element from the previous row as the leftmost number
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)
Repeat step three until there is a new row with one more number than the previous row
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 thus:

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

Computer program

The following is example code in the Ruby programming language that prints out all the Bell numbers from the 1st to the 300th inclusive (the limits can be adjusted)

#!/usr/bin/env ruby

def print_bell_numbers(start, finish)
# Initialize the Bell triangle as a two-dimensional array
triangle = Array[Array[1]]

# Make sure "start" is less than "finish", and both numbers are at least 1
(finish, start = start, finish) if finish < start
start = 1 if start < 1
finish = 1 if finish < 1

1.upto(finish-1) do |row_num|

# Set the first element of the current row to be the last element
# of the previous row
current_row = [triangle[row_num-1][row_num-1]]

# Calculate the rest of the elements in this row, then add the row
# to the Bell triangle
1.upto(row_num) do |col_num|
sum = triangle[row_num-1][col_num-1] + current_row[col_num-1]
current_row.push(sum)
end

triangle[row_num] = current_row

end

# Print out the Bell numbers
start.upto(finish) do |num|
puts triangle[num-1][0]
end
end

# Adjust the limits here
print_bell_numbers(1, 300)

And here an equivalent version written in Python

def bell_numbers(start, stop):
## Swap start and stop if start > stop
if stop < start: start, stop = stop, start
if start < 1: start = 1
if stop < 1: stop = 1

t = [[1]] ## Initialize the triangle as a two-dimensional array
c = 1 ## Bell numbers count
while c <= stop:
if c >= start:
yield t[-1][0] ## Yield the Bell number of the previous row
row = [t[-1][-1]] ## Initialize a new row
for b in t[-1]:
row.append(row[-1] + b) ## Populate the new row
c += 1 ## We have found another Bell number
t.append(row) ## Append the row to the triangle

for b in bell_numbers(1, 300):
print b

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.

And yet another very similar implementation, in Common Lisp

(defun print-bell-numbers (start finish)
"I print Bell numbers from B(start) up to and including B(finish),
where B(0) = B(1) = 1, start and finish range over integers >= 0."
(assert (and (integerp start) (integerp finish) (<= 0 start finish)))
(if (= start 0) (print (incf start))) ; B(0) is printed outside of the loop
(loop with a = '(1) ; first and current row in the bell triangle
for r from 1 to finish ; current row index
when (and (>= r start) (<= r finish)) do (print (car a))
do (loop with b = (list (car a)) ; the next row
for c in (reverse a) ; nreverse seems to be slower
do (push (+ c (car b)) b)
finally (setf a b)))) ; b becomes the new current row

(print-bell-numbers 0 299)

Prime Bell numbers

The first few Bell numbers that are primes are:

2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 (sequence A051131 in OEIS)

corresponding to the indices 2, 3, 7, 13, 42 and 55 (sequence A051130 in OEIS).

The next prime is B2841, which is approximately 9.30740105 × 106538.[2] As of 2006, it is the largest known prime Bell number. Phil Carmody showed it was a probable prime in 2002. After 17 months of computation with Marcel Martin's ECPP program Primo, Ignacio Larrosa Cañestro proved it to be prime in 2004. He ruled out any other possible primes below B6000, later extended to B30447 by Eric Weisstein.
See also

Bell polynomials
Ordered Bell numbers – the number of weak orders
Stirling numbers of the second kind – the number of ways to partition a set of n elements into k nonempty subsets.

References

^ Spivey, Michael (2008). "A Generalized Recurrence for Bell Numbers". Journal of Integer Sequences 11.
^ [1]

Gian-Carlo Rota (1964). "The Number of Partitions of a Set". American Mathematical Monthly 71 (5): 498–504. doi:10.2307/2312585. MR0161805.
Lovász, L. (1993). Combinatorial Problems and Exercises (2nd ed. ed.). Amsterdam, Netherlands: North-Holland.
Berend, D.; Tassa, T. (2010). "Improved Bounds on Bell Numbers and on Moments of Sums of Random Variables". Probability and Mathematical Statistics 30 (2): 185–205.

External links

Robert Dickau. "Diagrams of Bell numbers".
Pat Ballew. "Bell numbers".
Weisstein, Eric W., "Bell Number" from MathWorld.
Wagstaff, Samuel S. (1996). "Aurifeuillian factorizations and the period of the Bell numbers modulo a prime". Mathematics of computation 65 (213): 383–391. Bibcode 1996MaCom..65..383W. doi:10.1090/S0025-5718-96-00683-7. MR1325876.
Gottfried Helms. "Further properties & Generalization of Bell-Numbers".