The Bell number is the number of ways to partition a set of distinct elements into nonempty, mutually disjoint blocks. Neither the order of the blocks nor the order of elements within a block matters. Bell numbers are fundamental in combinatorics and arise in the study of equivalence relations, generating functions, probability, and classification problems. The sequence begins
Definition and examples
A set partition of a finite set is a collection of nonempty subsets, called blocks, such that each element of belongs to exactly one block. The number of such partitions depends only on the number of elements of , not on their identities.
For , the five partitions are
Thus .
By convention, : the empty set has exactly one partition, the empty collection of blocks. This is different from a collection containing an empty block, which is not a valid partition.
Every partition determines an equivalence relation: two elements are equivalent precisely when they lie in the same block. Conversely, the equivalence classes of an equivalence relation form a partition. Consequently, also counts the equivalence relations on an -element set.
Bell numbers should not be confused with counts of integer partitions. In a set partition the elements are distinguishable; in an integer partition only the sizes of the parts matter.
Recurrence relation
The Bell numbers satisfy the recurrence relation
where is a binomial coefficient.
To establish this identity, distinguish one element in a set of elements. Choose the elements that do not belong to its block. These can be chosen in ways and partitioned in ways. All remaining elements belong to the distinguished element’s block. Summing over counts every partition exactly once.
For example,
Bell triangle
An elementary way to compute the sequence is the Bell triangle, also called the Aitken triangle:
Each row begins with the final entry of the preceding row. Each subsequent entry is the sum of the entry immediately to its left and the entry above-left. With rows numbered from zero, the first entry of row is , and the last is .
The triangle computes all Bell numbers through using additions and stored integers if only the current row is retained. These bounds count arithmetic operations and stored integers; they do not account for the increasing number of digits in the entries.
Connection with Stirling numbers
The Stirling number of the second kind counts partitions of an -element set into exactly nonempty blocks. Therefore,
The Stirling numbers satisfy
The new element either joins one of existing blocks or forms a singleton block.
A related identity expresses an ordinary power in terms of falling factorials:
where
The Touchard polynomial
records the number of blocks by a variable. Bell numbers are its values at :
Exponential generating function
The exponential generating function of the Bell numbers is
where denotes the factorial of .
The inner expression
represents a nonempty block of labeled elements. The outer exponential function accounts for an unordered collection of such blocks.
Differentiating gives
Comparing coefficients recovers the Bell recurrence. The identity can be treated as an identity of formal power series; analytically, the series converges for every complex .
More generally, the Touchard polynomials have generating function
Dobiński’s formula and probability
Dobiński’s formula expresses each Bell number as an infinite sum:
Here is Euler’s number. For , the term is interpreted as .
The formula follows by expanding the generating function:
and comparing coefficients of .
It also has a direct probabilistic interpretation. If has a Poisson distribution with parameter , then
so
Thus Bell numbers are the raw moments of a Poisson random variable with mean , where denotes expected value. More generally, if has a Poisson distribution with parameter , then
Although Dobiński’s formula is exact, its infinite sum and noninteger intermediate quantities generally make recurrence-based methods more convenient for exact integer computation.
Growth and congruences
Bell numbers grow faster than any fixed-base exponential , but more slowly than . A useful logarithmic estimate is
Here denotes the natural logarithm, and the error term uses big-O notation. The estimate describes growth on a logarithmic scale; it is not by itself a relative-error approximation for .
Bell numbers also satisfy identities in modular arithmetic. Touchard’s congruence states that, for every prime and every integer ,
For , this becomes
Starting from , the parity pattern repeats as . Hence is even exactly when .
Applications and related counts
Bell numbers measure the number of possible groupings when objects are distinguishable but groups are unlabeled.
- Clustering: There are possible partitions of observations if any number of nonempty clusters is allowed. This is the unconstrained combinatorial search space for cluster analysis, not the number of outputs of a particular clustering algorithm.
- Relations and classification: Equivalence relations on a finite set correspond exactly to its partitions.
- Graph theory: In graph theory, counts labeled simple graphs on vertices whose connected components are all complete graphs. Each block specifies one complete component.
- Probability: Bell numbers arise as Poisson moments and in formulas that organize products of random variables by partitions.
Different conventions lead to different counts. If exactly unlabeled nonempty groups are required, the count is . If those groups receive distinct labels, the count becomes . If every group must have size two, only pair partitions are counted, not all Bell partitions.
Historical background
The sequence is named after Eric Temple Bell, who studied these numbers in the 1930s under the name “exponential numbers.” The partition-counting sequence and several of its formulas predate his work. Dobiński’s infinite-series formula dates to 1877.