Bell numbers

The nth Bell number is the number of ways to partition a set of n labeled items. It’s also equal to the following sum.

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

You may have to look at that sum twice to see it correctly. It looks a lot like the sum for eⁿ except the roles of k and n are reversed in the numerator.

The sum reminded me of the equation

$\frac{d}{de}e^x = x e^{x-1}$

that I blogged about a few weeks ago. It’s correct, but you may have to stare at it a little while to see why.

Incidentally, the nth Bell number is the nth moment of a Poisson random variable with mean 1.

There’s also a connection with Bell polynomials. The nth Bell number is the sum of the coefficients of the nth complete Bell polynomial. The nth Bell polynomial is sum over k of the partial exponential Bell polynomials B_n,k. The partial (exponential) Bell polynomials are defined here.

Computing Bell numbers

You can compute Bell numbers in Python with sympy.bell and in Mathematical with BellB. You can compute Bell numbers by hand, or write your own function in a language that doesn’t provide one, with the recursion relation B₀ = 1 and

$B_n = \sum_{k=0}^{n-1}{ n-1 \choose k}B_k$

for n > 0. Bell numbers grow very quickly, faster than exponential, so you’ll need extended precision integers if you want to compute very many Bell numbers.

For theoretical purposes, it is sometimes helpful to work with the exponential generating function of the Bell numbers. The nth Bell number is n! times the coefficient of xⁿ in exp(exp(x) – 1).

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

An impractical but amusing way to compute Bell numbers would be via simulation, finding the expected value of nth powers of random draws from a Poisson distribution with mean 1.

Computing Bell numbers

Related