Bell number
In combinatorial mathematics, the Bell numbers count the possible partitions of a set.
These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan.
In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.
[1] As well as appearing in counting problems, these numbers have a different interpretation, as moments of probability distributions.
is a squarefree positive integer, meaning that it is the product of some number
= 5 factorizations: The Bell numbers also count the rhyme schemes of an n-line poem or stanza.
Thus, the 15 possible four-line rhyme schemes are AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, and ABCD.
[1] The Bell numbers come up in a card shuffling problem mentioned in the addendum to Gardner 1978.
Of these, the number that return the deck to its original sorted order is exactly Bn.
Thus, the probability that the deck is in its original order after shuffling it in this way is Bn/nn, which is significantly larger than the 1/n!
Related to card shuffling are several other problems of counting special kinds of permutations that are also answered by the Bell numbers.
The permutations that avoid the generalized patterns 12-3, 32-1, 3-21, 1-32, 3-12, 21-3, and 23-1 are also counted by the Bell numbers.
The Bell numbers can easily be calculated by creating the so-called Bell triangle, also called Aitken's array or the Peirce triangle after Alexander Aitken and Charles Sanders Peirce.
The Bell numbers satisfy a recurrence relation involving binomial coefficients:[7] It can be explained by observing that, from an arbitrary partition of n + 1 items, removing the set containing the first item leaves a partition of a smaller set of k items for some number k that may range from 0 to n. There are
is the number of ways to partition a set of cardinality n into exactly k nonempty subsets.
Other finite sum formulas using Stirling numbers of the first kind include[9]
The exponential generating function of the Bell numbers is In this formula, the summation in the middle is the general form used to define the exponential generating function for any sequence of numbers, and the formula on the right is the result of performing the summation in the specific case of the Bell numbers.
One way to derive this result uses analytic combinatorics, a style of mathematical reasoning in which sets of mathematical objects are described by formulas explaining their construction from simpler objects, and then those formulas are manipulated to derive the combinatorial properties of the objects.
In the language of analytic combinatorics, a set partition may be described as a set of nonempty urns into which elements labelled from 1 to n have been distributed, and the combinatorial class of all partitions (for all n) may be expressed by the notation Here,
is a combinatorial class with only a single member of size one, an element that can be placed into an urn.
operator describes a set or urn that contains one or more labelled elements, and the outer
The exponential generating function may then be read off from this notation by translating the
operator into the exponential function and the nonemptiness constraint ≥1 into subtraction by one.
[10] An alternative method for deriving the same generating function uses the recurrence relation for the Bell numbers in terms of binomial coefficients to show that the exponential generating function satisfies the differential equation
[11][12][13] The Bell numbers satisfy Dobinski's formula[14][11][13] This formula can be derived by expanding the exponential generating function using the Taylor series for the exponential function, and then collecting terms with the same exponent.
[10] It allows Bn to be interpreted as the nth moment of a Poisson distribution with expected value 1.
[17][18] The period of the Bell numbers to modulo n are An application of Cauchy's integral formula to the exponential generating function yields the complex integral representation Some asymptotic representations can then be derived by a standard application of the method of steepest descent.
The first few Bell primes are: corresponding to the indices 2, 3, 7, 13, 42 and 55 (sequence A051130 in the OEIS).
[29] The first exhaustive enumeration of set partitions appears to have occurred in medieval Japan, where (inspired by the popularity of the book The Tale of Genji) a parlor game called genji-ko sprang up, in which guests were given five packets of incense to smell and were asked to guess which ones were the same as each other and which were different.
The 52 possible solutions, counted by the Bell number B5, were recorded by 52 different diagrams, which were printed above the chapter headings in some editions of The Tale of Genji.
