Bell number
Encyclopedia
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 relation
s on it. Starting with B_{0} = B_{1} = 1, the first few Bell numbers are:
(See also breakdown by number of subsets/equivalence classes.)
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_{3} = 5 because the 3element set {a, b, c} can be partitioned in 5 distinct ways:
B_{0} 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:
They also satisfy "Dobinski's formula":
And they satisfy "Touchard's congruence": If p is any prime number
then
or, generalizing
Each Bell number is a sum of Stirling numbers of the second kind
The Stirling number 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:
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 cumulant
s; 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
Here
where W is the Lambert W function.
(Lovász
, 1993)
In (Berend, D. and Tassa, T., 2010), the following bounds were established:
moreover, if then for all ,
where and
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:
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).
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.
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:
The fifth row is calculated thus:
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, the nth Bell number, named after Eric Temple Bell
Eric Temple Bell
Eric Temple Bell , was a mathematician and science fiction author born in Scotland who lived in the U.S. for most of his life...
, is the number of partitions
Partition of a set
In mathematics, a partition of a set X is a division of X into nonoverlapping and nonempty "parts" or "blocks" or "cells" that cover all of X...
of a set with n members, or equivalently, the number of equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
s on it. Starting with B_{0} = B_{1} = 1, the first few Bell numbers are:
 1, 1, 2, 5, 1515 (number)15 is the natural number following 14 and preceding 16. In English, it is the smallest natural number with seven letters in its spelled name....
, 5252 (number)52 is the natural number following 51 and preceding 53.In mathematics:Fiftytwo is the 6th Bell number and a decagonal number...
, 203203 (number)203 is the natural number following 202 and preceding 204. It may be written as "two hundred three" or "two hundred and three".In mathematics:203 is the 6th Bell number, i.e. it is the number of partitions of a set of size 6...
, 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 partitionsPartition of a set
In mathematics, a partition of a set X is a division of X into nonoverlapping and nonempty "parts" or "blocks" or "cells" that cover all of X...
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_{3} = 5 because the 3element 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_{0} is 1 because there is exactly one partition of the empty set
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
. Every member of the empty set is a nonempty set (that is vacuously true
Vacuous truth
A vacuous truth is a truth that is devoid of content because it asserts something about all members of a class that is empty or because it says "If A then B" when in fact A is inherently false. For example, the statement "all cell phones in the room are turned off" may be 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} }.
Another view of Bell numbers
Bell numbers can also be viewed as the number of distinct possible ways of putting n distinguishable balls into one or more indistinguishable 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: All three balls go in to one box. Since the boxes are anonymous, this is only considered one combination.
 a goes into one box; b and c go in to another box.
 b goes into one box; a and c go in to another box.
 c goes into one box; a and b go in to another box.
 Each ball goes in to its own box.
Properties of Bell numbers
The Bell numbers satisfy this recursion formula:They also satisfy "Dobinski's formula":

 = the nth momentMoment (mathematics)In mathematics, a moment is, loosely speaking, a quantitative measure of the shape of a set of points. The "second moment", for example, is widely used and measures the "width" of a set of points in one dimension or in higher dimensions measures the shape of a cloud of points as it could be fit by...
of a Poisson distributionPoisson distributionIn probability theory and statistics, the Poisson distribution is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time and/or space if these events occur with a known average rate and independently of the time since...
with expected valueExpected valueIn probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...
1.
 = the nth moment
And they satisfy "Touchard's congruence": If p is any prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
then
or, generalizing
Each Bell number is a sum of Stirling numbers of the second kind
The Stirling number 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:
The nth Bell number is also the sum of the coefficients in the polynomial that expresses the nth moment
Moment (mathematics)
In mathematics, a moment is, loosely speaking, a quantitative measure of the shape of a set of points. The "second moment", for example, is widely used and measures the "width" of a set of points in one dimension or in higher dimensions measures the shape of a cloud of points as it could be fit by...
of any probability distribution
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....
as a function of the first n cumulant
Cumulant
In probability theory and statistics, the cumulants κn of a probability distribution are a set of quantities that provide an alternative to the moments of the distribution. The moments determine the cumulants in the sense that any two probability distributions whose moments are identical will have...
s; this way of enumerating partitions is not as coarse as that given by the Stirling numbers.
The exponential generating function
Generating function
In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general...
of the Bell numbers is
Asymptotic limit and bounds
Several asymptotic formulae for the Bell numbers are known. One such isHere
where W is the Lambert W function.
(Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
, 1993)
In (Berend, D. and Tassa, T., 2010), the following bounds were established:
moreover, if then for all ,
where and
Triangle scheme for calculating Bell numbers
The Bell numbers can easily be calculated by creating the socalled Bell triangle, also called Aitken's array 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
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