Bell number

Lore & Background

The Bell numbers are denoted B_n, where n is an integer greater than or equal to zero. The Bell number B_n counts the different ways to partition a set that has exactly n elements, or equivalently, the equivalence relations on it. B_n also counts the different rhyme schemes for n-line poems. As well as appearing in counting problems, these numbers have a different interpretation, as moments of probability distributions. In particular, B_n is the n-th moment of a Poisson distribution with mean 1. In general, B_n is the number of partitions of a set of size n. For example, B_3 = 5 because the 3-element set {a,b,c} can be partitioned in 5 distinct ways. The partitions of a set correspond one-to-one with its equivalence relations. If a number N is a squarefree positive integer, meaning that it is the product of some number n of distinct prime numbers, then B_n gives the number of different multiplicative partitions of N. The Bell numbers also count the rhyme schemes of an n-line poem or stanza. The Bell numbers come up in a card shuffling problem: if a deck of n cards is shuffled by repeatedly removing the top card and reinserting it anywhere in the deck, with exactly n repetitions, then the number that return the deck to its original sorted order is exactly B_n.

Reader's Guide

The Bell numbers are a fundamental sequence in combinatorial mathematics, counting the partitions of a set. Their significance extends beyond pure enumeration: they also count equivalence relations, rhyme schemes for poetry, and multiplicative factorizations of squarefree numbers. In probability theory, they appear as moments of a Poisson distribution with mean 1. The numbers have been studied since the 19th century, with roots in medieval Japan, and are named after Eric Temple Bell due to Stigler's law of eponymy. They are denoted B_n, with B_0 = B_1 = 1, and the sequence grows rapidly. The Bell numbers also arise in card shuffling problems, where the probability of returning a deck to its original order after a specific shuffle is B_n / n^n. Additionally, they count certain permutations that avoid specific generalized patterns. The Bell numbers are distinct from ordered Bell numbers, which count ordered partitions. Their recurrence and triangle scheme for calculations make them accessible for study, and they appear in the OEIS as sequence A000110.

Did You Know?

• The Bell numbers count the possible partitions of a set.
• They have been studied since the 19th century, with roots in medieval Japan.
• B_n is the n-th moment of a Poisson distribution with mean 1.
• The Bell numbers also count rhyme schemes for n-line poems.

A Name That Doesn't Quite Fit

The Bell numbers carry a name that is, by mathematical convention, somewhat misleading. They are attributed to Eric Temple Bell, who discussed them in his 1930s writings, yet the sequence had already been explored by mathematicians throughout the nineteenth century, and its intellectual lineage stretches even further back to medieval Japanese scholarship. This is a textbook case of what statisticians call Stigler's law of eponymy: a result or object is typically named for the person who popularized it rather than the person who first discovered it. The numbers themselves, denoted B_n for integers n at least zero, begin with B_0 = B_1 = 1 and then climb through 2, 5, 15, 52, 203, 877, 4140, and so on—a sequence catalogued as A000110 in the Online Encyclopedia of Integer Sequences. Despite the somewhat accidental naming, the Bell numbers occupy a central place in combinatorics, bridging discrete counting, algebraic structure, and probability theory.

Counting the Ways to Divide

At their most fundamental level, the Bell numbers answer a deceptively simple question: given a collection of n distinct objects, in how many different ways can you group them together? A partition of a set S is a collection of nonempty, mutually exclusive subsets whose union recovers the entire set. For a three-element set {a, b, c}, the answer is five: all three elements in separate groups; a alone with b and c together; b alone with a and c together; c alone with a and b together; or all three lumped into a single group. The order in which you list the subsets does not matter—ordered groupings belong to a different sequence called the ordered Bell numbers. The base case B_0 = 1 might seem counterintuitive, but it follows from the fact that the empty set has exactly one partition: the empty family of subsets, which vacuously satisfies every required condition. Moreover, each partition corresponds bijectively to an equivalence relation on the set, meaning the Bell numbers equally count the number of reflexive, symmetric, and transitive binary relations one can define on n elements.

One Number, Many Countings

What makes the Bell numbers remarkable is that a single integer B_n simultaneously tallies several seemingly unrelated combinatorial objects. Beyond set partitions and equivalence relations, B_n counts the distinct rhyme schemes available for a poem of exactly n lines—each line assigned to a rhyme group, with the grouping structure mirroring a set partition. In number theory, if N is a squarefree positive integer that is the product of n distinct primes, then B_n gives the number of multiplicative factorizations of N into factors greater than one, where rearranging the order of factors does not produce a new factorization. For example, 30 = 2 × 3 × 5 has exactly B_3 = 5 such factorizations: 2×15, 3×10, 5×6, and 2×3×5 (the last being the fully split case). These parallel interpretations reveal a deep structural unity: in each context, the underlying operation is grouping n labeled items into an unordered collection of nonempty blocks, and the Bell number simply counts the possible block structures.

Beyond Counting: A Probabilistic Identity

The Bell numbers do not confine themselves to discrete combinatorics. They also carry a continuous, probabilistic interpretation that connects them to one of the most fundamental distributions in statistics. Specifically, B_n equals the n-th moment of a Poisson random variable with mean one. In other words, if X follows a Poisson distribution with parameter λ = 1, then the expected value of X to the n-th power equals B_n for every nonnegative integer n. This identity bridges the gap between the purely combinatorial world of set partitions and the analytic world of probability theory, suggesting that the same structural object—grouping n labeled items into unlabeled blocks—underlies both the counting of partitions and the moment-generating behavior of a Poisson process. The sequence 1, 1, 2, 5, 15, 52, 203, 877, 4140, and beyond thus appears not only in enumerative problems but also in the statistical description of rare-event processes, giving the Bell numbers a reach that extends well beyond their combinatorial origins.

Gallery