Bell Numbers

Bell numbers $B_n$ are named after Eric Temple Bell and form a sequence of integers in combinatorics. They begin as follows (OEIS A000110:

$B_n$ is the number of partitions of a set with cardinality $n$. A partition of a set $S$ is defined as a family of pairwise disjoint nonempty subsets of $S$ whose union is $S$. For example, $B_3 = 5$ because the set ${a, b, c}$ of 3 elements has 5 different partitions:

$B_0$ is 1 because the empty set has exactly 1 partition.

Recurrence

The Bell numbers satisfy the recurrence:

Proof:

$B_{n+1}$ is the number of partitions of a set containing $n+1$ elements. Let the set for $B_n$ be $\{b_1,b_2,b_3,\dots,b_n\}$ and the set for $B_{n+1}$ be $\{b_1,b_2,b_3,\dots,b_n,b_{n+1}\}$. Thus, $B_{n+1}$ can be regarded as being obtained from $B_{n}$ by adding one element, $b_{n+1}$. Consider the element $b_{n+1}$.

• If it is placed in a class by itself, $n$ elements remain, and the number of partitions in this case is $\dbinom{n}{n}B_{n}$;

• If it is placed in a class with some 1 element, $n-1$ elements remain, and the number of partitions in this case is $\dbinom{n}{n-1}B_{n-1}$;

• If it is placed in a class with some 2 elements, $n-2$ elements remain, and the number of partitions in this case is $\dbinom{n}{n-2}B_{n-2}$;

• ...

Continuing in this way gives the formula above.

Each Bell number is the sum of the corresponding Stirling numbers of the second kind. The Stirling numbers of the second kind are the number of ways to partition a set of cardinality $n$ into exactly $k$ nonempty sets.

Bell Triangle

Construct a triangular matrix as follows (in a form similar to Pascal's triangle):

• $a_{0,0} = 1$;
• For $n \ge 1$, the first entry of row $n$ equals the last entry of the previous row, namely $a_{n,0}=a_{n-1,n-1}$;
• For $m,n \ge 1$, the $n$-th row's $m$-th entry equals the sum of the entry to its left and the one to its upper left, namely $a_{n,m}=a_{n,m-1}+a_{n-1,m-1}$.

Some results are as follows:

The first entry of each row is a Bell number. The Bell numbers can be computed recursively using this triangle.

constexpr int MAXN = 2000 + 5;
int bell[MAXN][MAXN];

void f(int n) {
  bell[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    bell[i][0] = bell[i - 1][i - 1];
    for (int j = 1; j <= i; j++)
      bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1];
  }
}

MAXN = 2000 + 5
bell = [[0 for i in range(MAXN + 1)] for j in range(MAXN + 1)]


def f(n):
    bell[0][0] = 1
    for i in range(1, n + 1):
        bell[i][0] = bell[i - 1][i - 1]
        for j in range(1, i + 1):
            bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1]

Exponential Generating Function

Consider the exponential generating function of the Bell numbers and its derivative:

By the recurrence for the Bell numbers, we obtain:

This is a convolution, so:

This is a differential equation, whose solution is:

Finally, when $x = 0$, $\hat B(x) = 1$. Substituting gives $C = -1$, yielding the closed form of the exponential generating function of the Bell numbers:

After preprocessing $\mathrm{e}^x - 1$ through its first $n$ terms, one polynomial exp operation yields the first $n$ Bell numbers. The bottleneck is the polynomial exp operation, so the time complexity can be $O(n \log n)$.

References

https://en.wikipedia.org/wiki/Bell_number