Bell numbers

The numbers carry the name of Eric Temple Bell, the Scottish-born Caltech mathematician better known to general readers as the author of Men of Mathematics. Bell studied the Bell polynomials in a 1934 paper and wrote about the numbers themselves in 1938 — and took care to disclaim any discovery, noting that they had been investigated frequently and rediscovered many times. He cited earlier work going back to Dobiński, whose 1877 formula expresses the nth term as an infinite sum. Bell called them exponential numbers, after the generating function e^(eˣ − 1); the name "Bell numbers" and the symbol B(n) were attached by later writers, not by him.

The first exhaustive enumeration of set partitions seems to have happened in medieval Japan, and as entertainment rather than mathematics. The popularity of The Tale of Genji produced a parlour game called genjikō, in which guests were handed five packets of incense to smell and asked to say which were alike and which were different. There are exactly fifty-two possible answers — the Bell number B(5) — and all fifty-two were drawn as diagrams, which some editions of the novel print above the chapter headings. The fit is not quite perfect: the book runs to fifty-four chapters, so the emblem set has to be padded out.

Srinivasa Ramanujan investigated both the polynomials and the numbers in his second notebook. The triangular array that generates them, with Bell numbers running down both of its edges, has itself been found independently several times, which is why it answers to three names: the Bell triangle, Aitken's array, and the Peirce triangle, after Alexander Aitken and Charles Sanders Peirce. For a sequence whose defining feature is counting the ways a set can be broken apart, the scattered attribution is almost fitting.

Key properties

• B(n) counts the ways to partition a set of n labelled elements into non-empty, unordered blocks — equivalently, the number of equivalence relations on that set. B(0) = 1.
• The sequence opens 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975.
• B(n+1) = Σ C(n, k)·B(k) for k from 0 to n: pick the block containing a chosen element, then partition what is left.
• In the Bell triangle each row starts with the last entry of the row above and every later entry is the sum of the entry to its left and the one above-left; row n runs from B(n) to B(n+1).
• Dobiński's formula: B(n) = (1/e)·Σ kⁿ/k! over k ≥ 0, which also makes B(n) the nth moment of a Poisson distribution with mean 1.
• Touchard's congruence: B(n+p) ≡ B(n) + B(n+1) (mod p) for every prime p.
• B(7) = 877 and B(13) = 27,644,437 are prime; most Bell numbers are not.
• B(23) = 44,152,005,855,084,346 is the first Bell number to exceed 2^53 − 1, the largest integer a JavaScript number holds exactly.

Where they turn up

• Verse: the possible rhyme schemes for a stanza of n lines are exactly the partitions of those lines into rhyming groups, so there are B(n) of them — B(4) = 15 schemes for a quatrain, from aaaa to abcd.
• The genji-mon emblems used as chapter marks in editions of The Tale of Genji come from the fifty-two answers to the five-incense game — a cultural artefact of the count rather than a mathematical use of it.
• Clustering: with the number of groups left unspecified, the space of ways to cluster n items has size B(n), which is why exhaustive search is abandoned past small n and why Bayesian methods such as the Chinese restaurant process sample from the space instead.
• Statistics: because B(n) is the nth moment of a unit-rate Poisson distribution, the sequence shows up in moment calculations for arrival and queueing processes.
• Program analysis: the possible groupings of n variables into must-alias sets, or of n cases into equivalence classes, is a Bell number — the reason such analyses are built on incremental union-find rather than enumeration.