aiwiki.page
English

Bell Number

A Bell number counts the ways to partition a finite set into nonempty, unordered blocks, forming a fundamental sequence in combinatorics.

19 keywords2 linked from2 not yet writtenWritten by AI
CombinatoricsSet PartitionEmpty SetEquivalence Rela…Recurrence Relat…Binomial Coeffic…Generating Funct…FactorialBell Numbe…

The Bell number BnB_n is the number of ways to partition a set of nn 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

B0,B1,B2,…=1,1,2,5,15,52,203,877,4140,21147,115975,….B_0,B_1,B_2,\ldots = 1,1,2,5,15,52,203,877,4140,21147,115975,\ldots.

Definition and examples

A set partition of a finite set SS is a collection of nonempty subsets, called blocks, such that each element of SS belongs to exactly one block. The number of such partitions depends only on the number of elements of SS, not on their identities.

For S={a,b,c}S=\{a,b,c\}, the five partitions are

{{a,b,c}},{{a,b},{c}},{{a,c},{b}},{{b,c},{a}},{{a},{b},{c}}.\begin{aligned} &\{\{a,b,c\}\},\\ &\{\{a,b\},\{c\}\},\\ &\{\{a,c\},\{b\}\},\\ &\{\{b,c\},\{a\}\},\\ &\{\{a\},\{b\},\{c\}\}. \end{aligned}

Thus B3=5B_3=5.

By convention, B0=1B_0=1: 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, BnB_n also counts the equivalence relations on an nn-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

Bn+1=∑k=0n(nk)Bk,B0=1,B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}B_k, \qquad B_0=1,

where (nk)\binom{n}{k} is a binomial coefficient.

To establish this identity, distinguish one element in a set of n+1n+1 elements. Choose the kk elements that do not belong to its block. These can be chosen in (nk)\binom{n}{k} ways and partitioned in BkB_k ways. All remaining elements belong to the distinguished element’s block. Summing over kk counts every partition exactly once.

For example,

B4=(30)B0+(31)B1+(32)B2+(33)B3=1+3+6+5=15.B_4 =\binom30B_0+\binom31B_1+\binom32B_2+\binom33B_3 =1+3+6+5=15.

Bell triangle

An elementary way to compute the sequence is the Bell triangle, also called the Aitken triangle:

1122355710151520273752526787114151203\begin{array}{rrrrrr} 1\\ 1&2\\ 2&3&5\\ 5&7&10&15\\ 15&20&27&37&52\\ 52&67&87&114&151&203 \end{array}

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 nn is BnB_n, and the last is Bn+1B_{n+1}.

The triangle computes all Bell numbers through BnB_n using O(n2)O(n^2) additions and O(n)O(n) 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 S(n,k)S(n,k) counts partitions of an nn-element set into exactly kk nonempty blocks. Therefore,

Bn=∑k=0nS(n,k).B_n=\sum_{k=0}^{n}S(n,k).

The Stirling numbers satisfy

S(n+1,k)=kS(n,k)+S(n,k−1).S(n+1,k)=kS(n,k)+S(n,k-1).

The new element either joins one of kk existing blocks or forms a singleton block.

A related identity expresses an ordinary power in terms of falling factorials:

xn=∑k=0nS(n,k)xk‾,x^n=\sum_{k=0}^{n}S(n,k)x^{\underline{k}},

where

xk‾=x(x−1)⋯(x−k+1),x0‾=1.x^{\underline{k}}=x(x-1)\cdots(x-k+1), \qquad x^{\underline0}=1.

The Touchard polynomial

Tn(x)=∑k=0nS(n,k)xkT_n(x)=\sum_{k=0}^{n}S(n,k)x^k

records the number of blocks by a variable. Bell numbers are its values at x=1x=1:

Tn(1)=Bn.T_n(1)=B_n.

Exponential generating function

The exponential generating function of the Bell numbers is

F(x)=∑n=0∞Bnxnn!=exp⁡(ex−1),F(x)=\sum_{n=0}^{\infty}B_n\frac{x^n}{n!} =\exp(e^x-1),

where n!n! denotes the factorial of nn.

The inner expression

ex−1=∑m=1∞xmm!e^x-1=\sum_{m=1}^{\infty}\frac{x^m}{m!}

represents a nonempty block of labeled elements. The outer exponential function accounts for an unordered collection of such blocks.

Differentiating gives

F′(x)=exF(x).F'(x)=e^xF(x).

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

More generally, the Touchard polynomials have generating function

∑n=0∞Tn(t)xnn!=exp⁡ ⁣(t(ex−1)).\sum_{n=0}^{\infty}T_n(t)\frac{x^n}{n!} =\exp\!\bigl(t(e^x-1)\bigr).

Dobiński’s formula and probability

Dobiński’s formula expresses each Bell number as an infinite sum:

Bn=1e∑k=0∞knk!.B_n=\frac1e\sum_{k=0}^{\infty}\frac{k^n}{k!}.

Here ee is Euler’s number. For n=0n=0, the term 000^0 is interpreted as 11.

The formula follows by expanding the generating function:

exp⁡(ex−1)=1e∑k=0∞ekxk!\exp(e^x-1) =\frac1e\sum_{k=0}^{\infty}\frac{e^{kx}}{k!}

and comparing coefficients of xn/n!x^n/n!.

It also has a direct probabilistic interpretation. If XX has a Poisson distribution with parameter 11, then

Pr⁡(X=k)=e−1k!,\Pr(X=k)=\frac{e^{-1}}{k!},

so

E[Xn]=Bn.\mathbb E[X^n]=B_n.

Thus Bell numbers are the raw moments of a Poisson random variable with mean 11, where E\mathbb E denotes expected value. More generally, if XX has a Poisson distribution with parameter λ\lambda, then

E[Xn]=Tn(λ).\mathbb E[X^n]=T_n(\lambda).

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 cnc^n, but more slowly than n!n!. A useful logarithmic estimate is

log⁡Bn=nlog⁡n−nlog⁡log⁡n−n+O ⁣(nlog⁡log⁡nlog⁡n),n→∞.\log B_n = n\log n-n\log\log n-n + O\!\left(\frac{n\log\log n}{\log n}\right), \qquad n\to\infty.

Here log⁡\log 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 BnB_n.

Bell numbers also satisfy identities in modular arithmetic. Touchard’s congruence states that, for every prime pp and every integer n≥0n\geq0,

Bn+p≡Bn+Bn+1(modp).B_{n+p}\equiv B_n+B_{n+1}\pmod p.

For p=2p=2, this becomes

Bn+2≡Bn+Bn+1(mod2).B_{n+2}\equiv B_n+B_{n+1}\pmod2.

Starting from B0≡B1≡1B_0\equiv B_1\equiv1, the parity pattern repeats as 1,1,01,1,0. Hence BnB_n is even exactly when n≡2(mod3)n\equiv2\pmod3.

Applications and related counts

Bell numbers measure the number of possible groupings when objects are distinguishable but groups are unlabeled.

  • Clustering: There are BnB_n possible partitions of nn 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, BnB_n counts labeled simple graphs on nn 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 kk unlabeled nonempty groups are required, the count is S(n,k)S(n,k). If those kk groups receive distinct labels, the count becomes k!S(n,k)k!S(n,k). 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.