Bell number

Bell numbers are a sequence of integers used in combinatorial mathematics to count the total number of ways to partition a set. A partition is a way of splitting a collection of items into non-empty, separate groups. In these groups, every single item must belong to exactly one subset, and no two subsets can share the same item. These numbers are essential for understanding how different objects can be organized into distinct categories.

To understand how the mechanism works, consider a set of three distinct items. You could place each item in its own individual group, which results in one way to partition them. You could also put all three items into one single large group, which is another way. Finally, you could split them into one group of two items and one group of one item. There are actually several ways to choose which two items stay together. When you add all these possibilities up, you find there are five total ways to partition a three-element set. This total is the third Bell number, denoted as B3.

Bell numbers appear in several distinct mathematical contexts. One major type of application is in counting the rhyme schemes of poems. A rhyme scheme describes which lines in a stanza sound the same, which is essentially a partition of the lines into rhyming sets. For a four-line poem, there are exactly 15 different possible rhyme schemes, such as AAAA or ABAB. Another application involves multiplicative partitions of squarefree integers. If a number is the product of distinct prime numbers, the Bell number tells us how many ways we can factor it into groups of numbers greater than one. For example, the number 30 is the product of the primes 2, 3, and 5, and it has B3, or 5, different factorizations.

The history of these numbers spans many centuries and cultures. Their roots can be traced back to medieval Japan. During that era, traditional symbols for the 54 chapters of the "Tale of Genji" were based on the ways to partition five elements. This shows that the logic of Bell numbers was understood long before modern notation existed. In the 1930s, the mathematician Eric Temple Bell wrote about these numbers. Interestingly, the name "Bell number" is an example of Stigler's law of eponymy. This law suggests that people often name discoveries after those who popularized them, even if they were not the original discoverers.

You can calculate these numbers using a specific tool called the Bell triangle, also known as Aitken's array or the Peirce triangle. To build it, you start by writing the number 1 on the first row. To begin a new row, you take the rightmost number from the previous row and place it on the far left. To find the next numbers in that row, you add the number to your left to the number directly above that left-hand number. You continue this addition until the row is complete. The first number of each new row will always be a Bell number, and the sequence grows very quickly. For instance, B0 is 1, B1 is 1, B2 is 2, B3 is 5, and B4 is 15.

Bell numbers also have deep connections to probability and complex permutations. In probability, the nth Bell number represents the nth moment of a Poisson distribution that has a mean of 1. They also appear in specific card shuffling problems. If you shuffle a deck of $n$ cards by moving the top card to any position $n$ times, there are $n^n$ possible shuffles. Exactly $B_n$ of those shuffles will return the deck to its original, sorted order. This means the probability of the deck returning to order is $B_n/n^n$, which is much higher than a random shuffle.

Finally, these numbers relate to the study of prime numbers through "Bell primes." A Bell prime is a Bell number that is also a prime number, meaning it is only divisible by itself and one. These are quite rare and become incredibly large. The first few Bell primes are 2, 5, 877, and 27,644,437. As the index increases, the numbers grow to massive scales. For example, the sixth Bell prime, B55, is a number with 41 digits. Mathematicians still study whether there are infinitely many of these special primes.