Mathematics · Number Theory
Bell Number Calculator
Calculates the nth Bell number, representing the total number of distinct ways to partition a set of n elements into non-empty subsets.
Calculator
Formula
B_n is the nth Bell number. The recurrence builds each successive Bell number from all previous values using binomial coefficients. B_0 = 1 by convention (one way to partition the empty set). The binomial coefficient C(n, k) counts the number of ways to choose k elements from a set of n elements. Equivalently, Bell numbers appear as the row-leading values of the Bell triangle, where each row starts with the last element of the previous row and each subsequent element is the sum of the element to its left and the element directly above that left element.
Source: Bell, E. T. (1934). Exponential Numbers. American Mathematical Monthly, 41(7), 411–419. Also: Rota, G.-C. (1964). The Number of Partitions of a Set. American Mathematical Monthly, 71(5), 498–504.
How it works
A partition of a set S is a collection of non-empty, mutually disjoint subsets whose union equals S. The Bell number B(n) counts how many such partitions exist for a set of size n. For example, a set of 3 elements {a, b, c} can be partitioned in exactly 5 ways: {a,b,c} as one block; {a,b},{c}; {a,c},{b}; {b,c},{a}; and {a},{b},{c} — so B(3) = 5. These numbers arise naturally whenever you need to count groupings without regard to order within groups or order of the groups themselves.
The most computationally convenient method for calculating Bell numbers is the Bell triangle (also called Aitken's array or the Peirce triangle). Start with B(0) = 1 in the first row. Each subsequent row begins with the last element of the previous row, and each following element is the sum of the element immediately to its left and the element directly above that left element. The leading element of each row n gives B(n). The recurrence relation is B(n+1) = sum over k from 0 to n of C(n,k) × B(k), where C(n,k) is the binomial coefficient. This calculator implements the Bell triangle algorithm for exact integer results up to n = 25, where B(25) exceeds 4 trillion.
Bell numbers have applications in statistical mechanics (counting microstates), database theory (counting equivalence relations on a finite set), computational linguistics (phrase structure parsing), and graph theory. In probability and statistics, they appear when modeling random partitions, mixture models, and Bayesian nonparametric methods such as the Chinese restaurant process. Computer scientists use Bell numbers when analyzing the complexity of algorithms that must enumerate or search over all possible groupings of a dataset.
Worked example
Suppose you want to count how many ways a set of 4 elements — say {1, 2, 3, 4} — can be divided into non-empty subsets. We build the Bell triangle row by row:
Row 0: [1] → B(0) = 1
Row 1: Start with last element of Row 0 = 1. Next element = 1 + 1 = 2. Row 1: [1, 2] → B(1) = 1
Row 2: Start with last of Row 1 = 2. Elements: 2, 2+1=3, 3+2=5. Row 2: [2, 3, 5] → B(2) = 2
Row 3: Start with last of Row 2 = 5. Elements: 5, 5+2=7, 7+3=10, 10+5=15. Row 3: [5, 7, 10, 15] → B(3) = 5
Row 4: Start with last of Row 3 = 15. Elements: 15, 15+5=20, 20+7=27, 27+10=37, 37+15=52. Row 4: [15, 20, 27, 37, 52] → B(4) = 15
So there are exactly 15 distinct partitions of a 4-element set. These include 1 partition into a single block, 7 partitions into two blocks, 6 partitions into three blocks, and 1 partition into four singleton blocks (1 + 7 + 6 + 1 = 15 ✓). The Stirling numbers of the second kind S(4,k) for k = 1,2,3,4 are 1, 7, 6, 1 respectively, and they sum to B(4).
Limitations & notes
This calculator supports integer values of n from 0 to 25. Bell numbers grow extremely rapidly — B(25) = 4,638,590,332,960,756,480 — and exceed the safe integer range of JavaScript (2^53 − 1) for n greater than approximately 26, making exact computation unreliable without arbitrary-precision arithmetic. Negative values and non-integer inputs are not defined for Bell numbers. Bell numbers count unordered, unlabeled partitions; if you need ordered partitions or labeled groupings, you should instead use Stirling numbers of the second kind or ordered Bell numbers (Fubini numbers). Additionally, Bell numbers do not account for any structure within subsets — they treat all elements as distinguishable but all groupings as equally valid.
Frequently asked questions
What is the Bell number formula and how is it computed?
Bell numbers are most conveniently computed using the Bell triangle recurrence: each row starts with the last element of the previous row, and subsequent elements are sums of adjacent entries. The recurrence is B(n+1) = sum of C(n,k)×B(k) for k from 0 to n. This calculator uses the Bell triangle method for exact integer results.
What is the difference between Bell numbers and Stirling numbers?
Bell numbers B(n) count the total number of partitions of an n-element set into any number of non-empty subsets. Stirling numbers of the second kind S(n,k) count partitions of an n-element set into exactly k non-empty subsets. Bell numbers are the row sums of Stirling numbers: B(n) = S(n,1) + S(n,2) + ... + S(n,n).
What is B(0) and why is it 1?
B(0) = 1 by convention because there is exactly one way to partition the empty set: the empty partition itself (a partition with no subsets). This edge case is important for the recurrence to work correctly and is consistent with standard combinatorial conventions across set theory and combinatorics literature.
Where do Bell numbers appear in real-world applications?
Bell numbers appear in cluster analysis (counting ways to group data points), Bayesian nonparametrics (Chinese restaurant process), database design (counting equivalence relations), computational linguistics (counting parse trees), and statistical physics (counting microstates of bosonic systems). Any problem that asks 'in how many ways can this collection be grouped?' likely involves Bell numbers.
How fast do Bell numbers grow?
Bell numbers grow super-exponentially, faster than any polynomial or simple exponential. Roughly, log(B(n)) grows like n log(n). B(10) = 115,975 while B(20) = 51,724,158,235,372 — illustrating how quickly the count of set partitions explodes, which is why exhaustive enumeration of partitions becomes computationally infeasible for even moderate n.
Last updated: 2025-01-15 · Formula verified against primary sources.