Bell number
The Bell numbers form a sequence of positive integers in combinatorics, where the nth Bell number, denoted B_n, counts the total number of partitions of a set containing n distinct elements into nonempty unlabeled subsets.[1] These numbers arise naturally in problems involving the division of objects into groups without regard to order or labeling of the groups themselves.[1] Although named after the mathematician Eric Temple Bell, who analyzed them in a 1934 paper on partition polynomials, the sequence was first systematically studied by Srinivasa Ramanujan around 1904–1909 in his notebooks.[1] The first few Bell numbers are B_0 = 1, B_1 = 1, B_2 = 2, B_3 = 5, B_4 = 15, B_5 = 52, B_6 = 203, and B_7 = 877, exhibiting rapid exponential growth thereafter.[2] Combinatorially, B_n equals the sum of the Stirling numbers of the second kind S(n, k) over k = 0 to n, where S(n, k) counts the partitions into exactly k nonempty subsets.[1] Bell numbers hold significant importance in enumerative combinatorics, as they also count the number of equivalence relations on an n-element set and appear in the exponential generating function e^{e^x - 1} = \sum_{n=0}^\infty B_n \frac{x^n}{n!}.[1] Additional representations include Dobiński's formula, B_n = \frac{1}{e} \sum_{k=0}^\infty \frac{k^n}{k!}, which connects them to Poisson distribution expectations.[1] Their study extends to applications in probability, computer science for clustering algorithms, and number theory, including rare prime instances like B_2 = 2, B_3 = 5, and the massive B_{2841} proven prime in 2004.[1]Definition and examples
Definition
In combinatorics, the Bell number B_n denotes the total number of ways to partition a set with n elements into nonempty subsets.[3] A partition of a set S is a collection of nonempty subsets A_i \subseteq S such that \bigcup A_i = S and A_i \cap A_j = \emptyset for all i \neq j.[3] For example, consider the set \{1, 2, 3\}. Its partitions are \{\{1,2,3\}\}, \{\{1\}, \{2,3\}\}, \{\{2\}, \{1,3\}\}, \{\{3\}, \{1,2\}\}, and \{\{1\}, \{2\}, \{3\}\}, yielding B_3 = 5.[3] The Bell numbers satisfy the explicit formula B_n = \sum_{k=0}^n S(n,k), where S(n,k) is the Stirling number of the second kind, which counts the number of partitions of an n-element set into exactly k nonempty subsets.[3] By convention, B_0 = 1, corresponding to the single partition of the empty set.[3]Initial values
The initial Bell numbers provide concrete illustrations of the sequence's values for small nonnegative integers n, starting from the empty set. These numbers are obtained by systematically enumerating the distinct ways to partition sets with n elements.[2] The first sixteen Bell numbers, B_n for n = 0 to n = 15, are tabulated below to demonstrate their progression:| n | B_n |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 15 |
| 5 | 52 |
| 6 | 203 |
| 7 | 877 |
| 8 | 4140 |
| 9 | 21147 |
| 10 | 115975 |
| 11 | 678570 |
| 12 | 4213597 |
| 13 | 27644437 |
| 14 | 190899322 |
| 15 | 1382958545 |
Combinatorial interpretations
Set partitions
A set partition of a finite set S with n elements is a collection of nonempty subsets of S that are pairwise disjoint and whose union is exactly S. These subsets, called blocks, group the elements of S into distinct, non-overlapping groups without leaving any element unassigned. The Bell number B_n counts the total number of such partitions for any n-element set.[1] There exists a natural bijection between the set partitions of S and the equivalence relations on S. Specifically, given an equivalence relation \sim on S, the equivalence classes—sets of elements deemed equivalent under \sim—form a partition of S, with each class as a block. Conversely, any partition of S defines an equivalence relation where two elements are equivalent if and only if they belong to the same block. This correspondence highlights the structural equivalence between partitioning and relational grouping in set theory. The number of set partitions of an n-element set into exactly k blocks is given by the Stirling number of the second kind S(n,k), so B_n = \sum_{k=1}^n S(n,k). This partition perspective connects directly to surjective functions: the number of surjective (onto) functions from an n-element set to a k-element set is k! \, S(n,k), as each such function assigns elements to k labeled targets exhaustively, with the preimages forming an unordered partition into k blocks that can then be labeled in k! ways. Thus, while surjections emphasize ordered codomains, the underlying structure reverts to the unordered blocks of set partitions, underscoring the primacy of the partition interpretation for Bell numbers. To illustrate, consider the set S = \{1, 2, 3, 4\}, for which B_4 = 15. The partitions can be grouped by the number of blocks k:-
For k=1: 1 partition
\{\{1,2,3,4\}\} -
For k=2: 7 partitions
- One triple and one singleton (4 partitions):
\{\{1,2,3\},\{4\}\}, \{\{1,2,4\},\{3\}\}, \{\{1,3,4\},\{2\}\}, \{\{2,3,4\},\{1\}\} - Two doubletons (3 partitions):
\{\{1,2\},\{3,4\}\}, \{\{1,3\},\{2,4\}\}, \{\{1,4\},\{2,3\}\}
- One triple and one singleton (4 partitions):
-
For k=3: 6 partitions (each consisting of one doubleton and two singletons):
\{\{1,2\},\{3\},\{4\}\}, \{\{1,3\},\{2\},\{4\}\}, \{\{1,4\},\{2\},\{3\}\},
\{\{2,3\},\{1\},\{4\}\}, \{\{2,4\},\{1\},\{3\}\}, \{\{3,4\},\{1\},\{2\}\} -
For k=4: 1 partition
\{\{1\},\{2\},\{3\},\{4\}\}
Rhyme schemes
In poetry, a rhyme scheme specifies the pattern of end rhymes across the lines of a stanza, effectively partitioning the set of n lines into subsets where lines within each subset share the same rhyme sound.[4] This combinatorial structure aligns directly with the enumeration provided by Bell numbers, as each possible partitioning corresponds to a distinct rhyme scheme.[4] For a two-line stanza, the Bell number B_2 = 2 counts the schemes AA (both lines rhyme) and AB (lines rhyme differently).[4] With three lines, B_3 = 5 yields the schemes AAA (all rhyme), AAB (first two rhyme, third differs), ABA (first and third rhyme), ABB (last two rhyme), and ABC (all distinct).[4] This mapping mirrors the set partitions interpretation, where each block of the partition represents a group of lines assigned to the same rhyme sound, and distinct labels (such as A, B, C) differentiate the sounds across blocks.[4] As explored in the preceding section on set partitions, the total count of such configurations for n lines is the nth Bell number. The rhyme scheme application of Bell numbers has been utilized in linguistics and poetry analysis to systematically classify stanza structures and explore patterns in verse composition.[5]Factorizations
The Bell number B_n provides a combinatorial interpretation in number theory by counting the number of unordered factorizations of a square-free positive integer with exactly n distinct prime factors into integers greater than 1.[6] A square-free integer is one that is not divisible by any perfect square other than 1, meaning its prime factorization consists of distinct primes raised to the first power. For such an integer m = p_1 p_2 \cdots p_n, where p_i are distinct primes, an unordered factorization is a way to write m as a product f_1 f_2 \cdots f_k with each f_j > 1 and the order of the factors disregarded. The total number of such factorizations equals B_n, as each factorization corresponds uniquely to a partition of the set \{p_1, p_2, \dots, p_n\} into non-empty subsets, where each subset's product forms one factor f_j.[7] This bijection arises because grouping the primes into subsets mirrors the structure of set partitions: singleton subsets yield prime factors, while larger subsets yield composite factors from their products. For instance, the trivial partition into one block gives the single-factor representation m itself, while the partition into n singletons gives the full prime factorization. Since the factors are unordered, different permutations of the same grouping do not count as distinct, aligning precisely with the unordered nature of set partitions counted by B_n.[6] To illustrate, consider n = 1: Let m = 2. There is only one factorization: $2. This matches B_1 = 1. For n = 2: Let m = 6 = 2 \times 3. The factorizations are $6 (primes together) and $2 \times 3 (primes separate), giving 2 ways, matching B_2 = 2. For n = 3: Let m = 30 = 2 \times 3 \times 5. The factorizations are:- $30 (all primes together),
- $6 \times 5, $10 \times 3, $15 \times 2 (one pair and one singleton),
- $2 \times 3 \times 5 (all separate).
Permutations
The Bell number B_n enumerates the permutations of the set = \{1, 2, \dots, n\} that avoid the generalized pattern $1\mathbin{-}23.[8] In generalized pattern avoidance, the notation $1\mathbin{-}23 specifies an occurrence as indices i < j < j+1 \leq n in a permutation \pi where \pi(i) < \pi(j) < \pi(j+1), meaning an earlier entry smaller than an adjacent increasing pair later in the sequence. Thus, $1\mathbin{-}23-avoiding permutations are those with no such configuration, ensuring that every adjacent ascent is either at the start or lacks a smaller preceding value. This interpretation aligns with the known values of Bell numbers for small n. For n=1, the single permutation (1) avoids the pattern. For n=2, both $12 and $21 avoid it, as no valid triple exists. For n=3, the avoiding permutations are $132, $213, $231, $312, and $321; the permutation $123 contains an occurrence at positions $1,2,3 since $1 < 2 < 3. This yields 5 permutations, matching B_3 = 5. A bijection maps these avoiding permutations to set partitions of $$ by interpreting the permutation's structure—specifically, its descents and ascents—as defining partition blocks in a canonical decreasing order within blocks, with the avoidance condition preserving the partition's integrity. This connection highlights the combinatorial equivalence between the two objects.[8]Computation methods
Recurrence relations
The Bell numbers satisfy the initial condition B_0 = 1 and the recurrence relation B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k for n \geq 0.[1] This relation provides a direct method for iterative computation of successive Bell numbers from prior values. The recurrence follows from the combinatorial meaning of Bell numbers as the number of partitions of an (n+1)-element set S = \{1, 2, \dots, n+1\}. Consider the block containing the distinguished element n+1; this block includes n+1 together with some subset of k elements from \{1, 2, \dots, n\}, where $0 \leq k \leq n. There are \binom{n}{k} ways to choose this subset, and the remaining n - k elements can then be partitioned arbitrarily in B_{n-k} ways. Summing over all possible k and substituting j = n - k yields the given formula.[4] To illustrate, the computation of B_4 (assuming prior values B_0 = 1, B_1 = 1, B_2 = 2, B_3 = 5) proceeds as B_4 = \sum_{k=0}^3 \binom{3}{k} B_k = \binom{3}{0} B_0 + \binom{3}{1} B_1 + \binom{3}{2} B_2 + \binom{3}{3} B_3 = 1 \cdot 1 + 3 \cdot 1 + 3 \cdot 2 + 1 \cdot 5 = 15. Similar steps yield higher terms, such as B_5 = 52. Although the recurrence enables computation via dynamic programming in O(n^2) time to obtain B_n (as each of the n steps requires O(n) additions), practical limits arise for large n due to the super-exponential growth of the numbers themselves, which exceed standard integer precision beyond n \approx 1000 without specialized big-integer arithmetic.Bell triangle
The Bell triangle, also known as Aitken's array or the Peirce triangle, is a triangular array of natural numbers that facilitates the computation of Bell numbers through successive additions, much like Pascal's triangle but with a shifted starting point for each row.[9] The array is indexed by row number n \geq 0 and column index k = 0, 1, \dots, n, with entries denoted C(n,k). It begins with the single entry C(0,0) = 1. For n \geq 1, the first entry of each row is set to the last entry of the previous row: C(n,0) = C(n-1,n-1). Subsequent entries in the row are computed as C(n,k) = C(n,k-1) + C(n-1,k-1) for $1 \leq k \leq n. This construction directly yields the Bell numbers as the leftmost column C(n,0) = B_n for each n. The name "Bell triangle" refers to the Bell numbers appearing in the first column.[10] The following table illustrates the first six rows (up to n=5) of the Bell triangle:| n | k=0 | k=1 | k=2 | k=3 | k=4 | k=5 |
|---|---|---|---|---|---|---|
| 0 | 1 | |||||
| 1 | 1 | 2 | ||||
| 2 | 2 | 3 | 5 | |||
| 3 | 5 | 7 | 10 | 15 | ||
| 4 | 15 | 20 | 27 | 37 | 52 | |
| 5 | 52 | 67 | 87 | 114 | 151 | 203 |
Mathematical properties
Generating functions
The exponential generating function for the Bell numbers B_n is given by G(x) = \sum_{n=0}^\infty B_n \frac{x^n}{n!} = e^{e^x - 1}. This closed-form expression arises from the combinatorial interpretation of Bell numbers as the number of partitions of an n-element set.[11] To derive this, consider the exponential formula for labeled structures, which states that the exponential generating function for set partitions is the exponential of the generating function for the connected components (nonempty subsets). The exponential generating function for nonempty subsets of size n \geq 1 is \sum_{n=1}^\infty \frac{x^n}{n!} = e^x - 1, since each subset is a single block without further structure. Applying the exponential formula yields G(x) = e^{e^x - 1}, where the outer exponential accounts for the disjoint union of blocks forming the partition.[11][12] Alternatively, the formula can be obtained from the recurrence B_n = \sum_{k=0}^{n-1} \binom{n-1}{k} B_k with B_0 = 1. Multiplying by x^n / n! and summing over n \geq 1 leads to the differential equation G'(x) = e^x G(x) with G(0) = 1, whose solution is G(x) = e^{e^x - 1}.[13] The ordinary generating function \sum_{n=0}^\infty B_n x^n lacks a simple closed form but satisfies the functional equation B(x) = 1 + \frac{x}{1-x} B\left(\frac{x}{1-x}\right).[14] This exponential generating function facilitates derivations of other identities, such as expressing the raw moments of a Poisson random variable with parameter \lambda = 1, where the nth moment equals B_n.[15]Summation formulas
One explicit summation formula for the Bell number B_n expresses it as the sum of the Stirling numbers of the second kind S(n,k) from k=0 to n: B_n = \sum_{k=0}^n S(n,k), where S(n,k) denotes the number of ways to partition an n-element set into exactly k nonempty unlabeled subsets.[1] This relation follows directly from the combinatorial interpretation of Bell numbers as the total number of partitions of an n-element set, aggregating over all possible numbers of subsets. A well-known infinite summation formula, known as Dobiński's formula, provides another explicit expression: B_n = \frac{1}{e} \sum_{k=0}^\infty \frac{k^n}{k!}. This formula, first derived by Dobiński in 1877, arises from the exponential generating function for Bell numbers or through probabilistic arguments.[16] One derivation interprets the sum as the nth factorial moment of a Poisson random variable with parameter 1, which equals B_n due to the connection between set partitions and the moments of this distribution.[17] Numerical verification of Dobiński's formula holds for small values of n. For n=1, the sum is \frac{1}{e} (0^1/0! + 1^1/1! + 2^1/2! + 3^1/3! + \cdots) = \frac{1}{e} \cdot e = 1 = B_1. For n=2, it yields \frac{1}{e} (0 + 1 + 2/2 + 6/6 + 24/24 + \cdots) = 2 = B_2. For n=3, the partial sum up to k=10 approximates 5, matching B_3 = 5, with convergence improving for larger terms.[16]Asymptotic growth
The asymptotic growth of the Bell numbers B_n is characterized by a formula involving the Lambert W function, which provides a precise approximation for large n. Define r = W(n), the principal branch of the Lambert W function satisfying r e^r = n. Equivalently, let N = e^r, so that N \ln N = n. Then, B_n \sim \frac{N^n e^{N - n - 1}}{\sqrt{1 + \ln N}} as n \to \infty, with relative error O\left( \frac{(\ln n)^{1/2}}{n^{1/2}} \right).[18] This expression captures the dominant behavior, where the term N^n reflects the rapid exponential growth modulated by the saddle point determined by the generating function. This asymptotic was originally derived by Moser and Wyman using a method based on the integral representation of the Bell numbers via the exponential generating function \sum_{n=0}^\infty B_n \frac{x^n}{n!} = e^{e^x - 1}, applying a saddle-point approximation around the point where the integrand achieves its maximum contribution.[19] De Bruijn later refined the analysis, confirming the form through detailed expansion of the contour integral and error estimates. The Lambert W function emerges naturally as the solution to the transcendental equation defining the saddle point r, which asymptotically behaves as r \sim \ln n - \ln \ln n + o(1).[18] Compared to the factorial n!, which grows as \sim \sqrt{2\pi n} (n/e)^n or roughly \exp(n \ln n - n + O(\ln n)), the Bell numbers exhibit faster growth: \ln B_n \sim n \ln n - n \ln \ln n - n + O(n / \ln n). This places B_n between single-exponential functions like a^n and fully double-exponential ones like \exp(c^n), highlighting their superexponential yet sub-double-exponential nature in combinatorial enumeration.[18] For illustration, B_{10} = 115975 and the approximation yields a relative error below 1%, while for n=20, B_{20} \approx 5.17 \times 10^{13} with error under 0.1%.[20]Log-concavity
The sequence of normalized Bell numbers, a_n = \frac{B_n}{n!}, is log-concave, satisfying a_{n-1} a_{n+1} \leq a_n^2 for all n \geq 2, with equality holding only for small values of n. This property follows from the structure of the exponential generating function for the Bell numbers, \sum_{n=0}^\infty a_n x^n = e^{e^x - 1}, which preserves log-concavity through analytic continuation and coefficient extraction techniques. Alternatively, a proof can be sketched using the representation B_n = \sum_{k=0}^n S(n,k), where S(n,k) are the Stirling numbers of the second kind; the log-concavity arises inductively from the recurrence relations and positivity of these coefficients. A stronger underlying property is the total positivity of the Stirling triangle, where all minors of the matrix with entries S(n,k) are positive. This total positivity, as established by Karlin, implies the log-concavity of each row \{S(n,k)\}_{k=0}^n via the theory of variation-diminishing transformations and Pólya frequency sequences.[21] In turn, this row log-concavity contributes to the overall log-concavity of the normalized Bell sequence through summation and normalization.[21] The log-concavity of \{a_n\} has implications for combinatorial inequalities, such as bounding partial sums of Bell numbers and establishing unimodality in related partition statistics, which are useful in asymptotic analysis and probabilistic models of set partitions. For instance, it facilitates Newton's inequalities for the coefficients of the generating function, providing tighter estimates on growth compared to crude asymptotic approximations.Modular properties
The modular properties of Bell numbers have been studied extensively in number theory and combinatorics, particularly in relation to primes and the behavior of the sequence modulo p. A fundamental result is Touchard's congruence, which states that for any prime p and nonnegative integer n, B_{n+p} \equiv B_n + B_{n+1} \pmod{p}. This congruence, originally due to Jacques Touchard, allows recursive computation of Bell numbers modulo p and implies that the sequence {B_n \mod p} satisfies a linear recurrence of order 2 with periodic coefficients. As a consequence, B_p \equiv B_0 + B_1 = 2 \pmod{p}. The result follows from the explicit formula for Bell numbers in terms of Stirling numbers of the second kind and properties of falling factorials modulo p.[22] Another important congruence relates Bell numbers to derangement numbers D_m modulo p. For a prime p, B_{p-1} \equiv D_{p-1} + 1 \pmod{p}. Derangement numbers count permutations without fixed points, and for primes p > 2, D_{p-1} \equiv -1 \pmod{p} in many cases, though exceptions occur for small p (e.g., p=3 where D_2 = 1 \not\equiv -1 \pmod{3}). This yields B_{p-1} \equiv 0 \pmod{p} for p=5 (B_4=15 \equiv 0) and p=7 (B_6=203 \equiv 0), but B_2=2 \equiv -1 \pmod{3} for p=3. The congruence arises from generating function identities and evaluations at roots of unity modulo p.[22] The sequence of Bell numbers modulo a prime p is purely periodic, with the minimal period dividing N_p = p^{p-1}/(p-1). Computations show that the minimal period equals N_p for all primes p < 126 and several larger ones (e.g., p=137,149). For small p, this yields short observable patterns, but the full period grows rapidly. Touchard's congruence facilitates verifying periodicity by checking alignment after shifts of length N_p. Known bounds indicate that the minimal period does not divide any proper divisor of N_p involving small prime factors q of N_p, confirmed computationally up to p < 1100.[23] Examples for small primes illustrate these properties. The following table lists the first 12 Bell numbers modulo 2, 3, 5, and 7:| n | B_n mod 2 | B_n mod 3 | B_n mod 5 | B_n mod 7 |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 2 | 2 | 2 |
| 3 | 1 | 2 | 0 | 5 |
| 4 | 1 | 0 | 0 | 1 |
| 5 | 0 | 1 | 2 | 3 |
| 6 | 1 | 2 | 3 | 0 |
| 7 | 1 | 1 | 2 | 2 |
| 8 | 0 | 0 | 0 | 3 |
| 9 | 1 | 0 | 2 | 0 |
| 10 | 1 | 1 | 0 | 6 |
| 11 | 0 | 0 | 0 | 4 |
Integral representations
The exponential generating function for the Bell numbers is G(z) = e^{e^z - 1} = \sum_{n=0}^\infty B_n \frac{z^n}{n!}. Applying Cauchy's integral formula to extract the coefficient of z^n / n! yields the contour integral representation B_n = \frac{n!}{2\pi i} \oint_C \frac{e^{e^z - 1}}{z^{n+1}} \, dz, where C is any simple closed contour in the complex plane that encircles the origin positively and lies within the disk of analyticity of the integrand.[20] This representation plays a central role in analytic combinatorics, where it facilitates asymptotic analysis of B_n via techniques such as saddle-point integration, revealing the dominant growth behavior given by the asymptotic expansion in the previous subsection. A remarkable real integral representation, discovered by Ernesto Cesàro in 1885 and later corrected for a missing factorial factor, is B_n = \frac{2 n!}{\pi e} \Im \left( \int_0^\pi e^{e^{i\theta}} \sin(n \theta) \, d\theta \right) for n \geq 1.[25] This formula stems from expressing Bell numbers in terms of Stirling numbers of the second kind and exploiting the orthogonality of the sine functions over [0, \pi].[25] An equivalent fully real form expands the complex exponential: B_n = \frac{2 n!}{\pi e} \int_0^\pi e^{\cos \theta} \sin \left( e^{\cos \theta} \sin(\sin \theta) + n \theta \right) \, d\theta. [25] Both variants enable numerical evaluation of B_n and have been verified computationally for small n, such as B_1 = 1, B_2 = 2, and B_3 = 5.[25]Applications and variants
Probability distributions
The Bell numbers arise naturally in the study of moments for the Poisson distribution. Specifically, if K is a Poisson random variable with mean parameter 1, then the nth raw moment \mathbb{E}[K^n] equals the nth Bell number B_n. This equivalence follows from Dobiński's formula, which expresses B_n = e^{-1} \sum_{k=0}^\infty \frac{k^n}{k!}, precisely the form of the expectation \mathbb{E}[K^n] = \sum_{k=0}^\infty k^n \Pr(K = k) under the Poisson(1) probability mass function \Pr(K = k) = e^{-1} k!^{-1}.[16] This connection generalizes through the Touchard polynomials, defined as T_n(\lambda) = \sum_{k=0}^n S(n,k) \lambda^k, where S(n,k) are the Stirling numbers of the second kind. For a Poisson random variable X with mean parameter \lambda > 0, the nth raw moment is \mathbb{E}[X^n] = T_n(\lambda), so B_n = T_n(1).[26] The moment generating function provides a direct way to derive these moments. For K \sim \mathrm{[Poisson](/page/Poisson)}(1), the mgf is M(t) = \mathbb{E}[e^{tK}] = \exp(e^t - 1). The nth raw moment is then the nth derivative of M(t) evaluated at t = 0, which yields B_n. Equivalently, the exponential generating function for the Touchard polynomials is \sum_{n=0}^\infty T_n(\lambda) \frac{t^n}{n!} = e^{\lambda (e^t - 1)}, aligning with the mgf scaled by the factorial moments.[26] For illustration, consider small values of n: when n=1, B_1 = 1 = \mathbb{E}[K]; for n=2, B_2 = 2 = \mathbb{E}[K^2] = \mathrm{Var}(K) + (\mathbb{E}[K])^2 = 1 + 1; and for n=3, B_3 = 5 = \mathbb{E}[K^3], computed via the mgf or Touchard expansion T_3(1) = 1 + 3 \cdot 1 + 1 = 5. These examples highlight how the combinatorial structure of Bell numbers captures the higher-order moments of the Poisson(1) distribution.[27]Bell primes
A Bell prime is defined as a Bell number B_n that is also a prime number.[28] The smallest such primes occur for small indices: B_2 = 2, B_3 = 5, and B_7 = 877.[1] Further examples include B_{13} = 27{,}644{,}437, which was verified as prime using advanced primality testing algorithms.[28] Larger Bell primes are exceedingly rare due to the rapid, double-exponential growth of Bell numbers, which makes them susceptible to factorization despite their size.[1] The known indices n where B_n is prime are 2, 3, 7, 13, 42, 55, and 2841, with B_{42} (38 digits) and B_{55} (54 digits) having values exceeding $10^{30}, and B_{2841} having 6,539 digits.[28][29] The primality of B_{2841} was certified using the Primo software, a deterministic primality prover capable of handling massive integers.[28] Checking primality for large Bell numbers typically involves probabilistic tests such as the Miller-Rabin algorithm for initial screening, followed by deterministic methods like the AKS test or specialized provers for confirmation.[1] Modular properties of Bell numbers can occasionally aid in identifying factors for smaller composite cases, though this is less effective for enormous primes like B_{2841}.[28] No additional Bell primes have been identified beyond n=2841 as of November 2025, underscoring their scarcity.[28]Historical development
Early computations
Even earlier, in 1321, the Persian mathematician Kamāl al-Dīn al-Fārisī listed Bell numbers up to B_8 in a work on astronomy, predating both Japanese and European efforts.[30] In the 18th century, Japanese mathematician Yoshisuke Matsunaga (1694?–1744) made significant early contributions to the computation of Bell numbers during the Edo period, motivated by problems in Genjikō combinatorics, a traditional game involving arrangements of stones. In his 1726 manuscript Danren Sōjutsu, Matsunaga developed a method using what are now known as Matsunaga numbers (related to signed Stirling numbers of the first kind) to calculate Bell numbers via the relation B_n = 1 + \frac{1}{n!} \sum_{k=1}^n M_{n,k} n^k, where M_{n,k} are the Matsunaga numbers. He computed values up to B_8 = 4140, including B_2 = 2, B_3 = 5, B_4 = 15, B_5 = 52, B_6 = 203, B_7 = 877, employing tabular methods and Horner's rule for efficiency. Matsunaga's work remained unpublished during his lifetime, but it was extended and popularized by Yoriyuki Arima (1714–1783) in his 1763 book Danren Henkyokuhō. Arima refined the recurrence to B_n = \sum_k \binom{n-1}{k} B_{n-1-k} and computed Bell numbers up to B_{13} = 27644437, solving for B_{11} = 678570 in a 1769 problem from Shūki Sanpō. These calculations predated known European efforts and were part of the Wasan tradition, linking set partitions to combinatorial games without explicit recognition of the numbers' broader significance. In Europe, sequences of Bell numbers appeared as early as 1796 by Christian Kramp, with further listings in works like Whitworth's 1870 Choice and Chance in the context of partitions, though without a general formula. In 1877, Gustaw Dobiński provided the first explicit formula, B_n = \frac{1}{e} \sum_{k=0}^\infty \frac{k^n}{k!}, enabling computations beyond small n. A key advancement came in 1880 when American philosopher and mathematician Charles Sanders Peirce independently discovered the Bell triangle (also known as the Peirce triangle), a recursive array for computing Bell numbers displaying the Stirling numbers of the second kind S(n,k), where each entry satisfies S(n,k) = S(n-1,k-1) + k \, S(n-1,k), with S(n,0) = 0, S(0,k) = 0 for k > 0, S(0,0) = 1, and the row sums giving the Bell numbers. Peirce used this in his algebraic logic framework to enumerate logical associations, computing values up to at least B_{10} = 115975. The triangle provided an efficient tabular method, akin to Pascal's triangle, for generating the sequence:| Row | Entries (partial) | Bell Number (sum) |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1 | 1 |
| 2 | 1 1 | 2 |
| 3 | 1 3 1 | 5 |
| 4 | 1 7 6 1 | 15 |
| 5 | 1 15 25 10 1 | 52 |