Every Way to Split a Set — What a Bell Number Calculator Counts
About the Author
Marko Šinko
Co-Founder & Lead Developer, AI Math Calculator
Ask a Bell number calculator for B(3) and it says 5. Ask for B(10) and it says 115,975. Ask for B(100) and it hands back a 116-digit integer. Nothing about the question got harder in between — B(n) is always just “how many ways can n labelled things be split into groups?” — but the answer went from something you can list on a napkin to something that dwarfs the roughly 1080 atoms in the observable universe.
That jump is the reason this sequence needs a tool rather than a formula you memorise. Below: where B(n) sits between 2n and n!, the triangle that computes it with nothing but addition, the binomial identity behind it, an infinite series that somehow returns an integer, and the modular trick that lets programmers get B(10,000) without ever holding a 26,000-digit number in memory.
B(n) Outruns Every Exponential and Still Loses to n!
Three counts get confused with each other constantly, and separating them is most of the battle. For ten items: 210 = 1,024 subsets, B(10) = 115,975 partitions, and 10! = 3,628,800 orderings. The gaps widen fast.
| n | 2ⁿ (subsets) | B(n) (partitions) | n! (orderings) |
|---|---|---|---|
| 4 | 16 | 15 | 24 |
| 10 | 1,024 | 115,975 | 3,628,800 |
| 20 | 1,048,576 | 51,724,158,235,372 | 2.43 × 10¹⁸ |
| 100 | 31 digits | 116 digits | 158 digits |
Notice the crossover at n = 4, where 15 partitions still lose to 16 subsets. At n = 5 the partitions win (52 against 32) and never look back. Meanwhile factorials stay ahead the whole way, and the ratio keeps growing: 10! is 31 times B(10), while 100! is roughly 1042 times B(100).
There is a clean way to state where B(n) lives. The step ratio B(n)/B(n−1) is about 8.9 at n = 20 and about 29.4 at n = 100 — it climbs, unlike an exponential where the ratio is fixed, but it climbs more slowly than n, which is what the ratio would be for a factorial. Precisely, ln B(n)/n → ln n − ln ln n − 1. Bell numbers are the sequence that sits in the gap where “exponential” and “factorial” stop being useful words.
A Triangle Built From Nothing but Addition
The practical method for computing B(n) by hand is a triangular array usually credited to Aitken and Peirce. Three rules run it, and the first is just the base case:
- Start row 0 with a single 1.
- Every new row begins with the last entry of the row above it.
- Every other entry equals its left neighbour plus the entry diagonally above-left.
Building five rows takes about thirty seconds:
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
Row 3 is worth walking through. It begins with 5 because 5 ended row 2. Then 5 + 2 = 7 (left neighbour 5, above-left 2), then 7 + 3 = 10, then 10 + 5 = 15. The Bell numbers are the left edge reading down — 1, 1, 2, 5, 15, 52 — and they are equally the right edge shifted by one row, which is exactly why the copy-down rule works.
Two things make this the method worth knowing. It uses no multiplication, no division, and no subtraction, so nothing can overflow into a fraction or cancel catastrophically. And each entry depends only on the row above, so a program needs one row in memory rather than the whole triangle. That is O(n²) additions and O(n) space — a very different profile from the Pascal triangle behind the binomial theorem, which looks similar on the page but is symmetric and builds each entry from two cells directly above rather than one above and one beside.
Why B(n+1) = Σ C(n,k)·B(k) Is Really a Question About One Element
The identity most textbooks lead with looks heavier than the triangle:
It has a one-sentence proof. Fix the newest element and ask how many of the other n elements are not in its block. Call that number k. Choose which k those are — C(n,k) ways — and then partition just those k among themselves, in B(k) ways. Everything left over is forced into the newest element’s block. No partition is counted twice, because k is determined by the partition itself.
Run it at n = 3 to get B(4): C(3,0)·B(0) + C(3,1)·B(1) + C(3,2)·B(2) + C(3,3)·B(3) = 1·1 + 3·1 + 3·2 + 1·5 = 1 + 3 + 6 + 5 = 15. The calculator above lays this out term by term for whatever n you enter, which makes it easy to see where the weight sits: at large n the middle terms dominate, because a combination like C(99,50) is astronomically bigger than C(99,0).
As an algorithm this identity is worse than the triangle. It needs binomial coefficients, which means either a second table or a multiply-and-divide per term, and it does the same O(n²) work with far larger intermediate values. Use it for proofs and for generating function derivations — it is what gives the exponential generating function ee^x − 1 — and use the triangle when you actually want a number.
An Infinite Series That Lands Exactly on an Integer
Dobiński’s formula from 1877 is the strangest fact in this subject:
An irrational constant, an infinite sum, and the result is always a whole number. Test it at n = 2: the sum 0 + 1 + 4/2 + 9/6 + 16/24 + 25/120 + … converges to 2e ≈ 5.4366, and dividing by e gives exactly 2 = B(2). The terms rise, peak somewhere near k = n, then collapse under the factorial, so the series converges fast enough to check on a phone.
The probabilistic reading explains why it is true. If X is a Poisson random variable with mean 1, then P(X = k) = e−1/k!, so the formula says B(n) = E[Xn] — the nth moment of a Poisson(1) distribution. Bell numbers are moments, which is also where the average block count comes from: a partition of an n-set picked uniformly at random has B(n+1)/B(n) − 1 blocks on average, about 4.85 for n = 10 and 28.6 for n = 100.
Do not compute with Dobiński’s formula. A double carries 53 bits of mantissa, so B(23) = 44,152,005,855,084,346 is already too big to represent exactly, and the division by an irrational e guarantees error in precisely the last digits you were trying to pin down. It is a proof technique and an asymptotics tool, not an algorithm.
How a Bell Number Calculator Reaches B(10,000) Mod a Prime
Contest problems ask for B(n) modulo 1,000,000,007 for a reason: the exact value is unusable. B(10,000) has about 26,000 digits. The fix is that the Bell triangle only ever adds, and addition commutes with taking a remainder, so you can reduce every single entry as you build:
Each entry stays under m, every addition is a machine-word operation, and the whole computation is O(n²) with n numbers of memory. On an n of 10,000 that is 50 million additions — under a second in C or C++, a minute or so in pure Python. The calculator above uses exact BigInt arithmetic and then reduces at the end, which is the honest thing to do for a page that also shows the full value, but the reduce-as-you-go version is what belongs in a submission.
There is also a genuinely surprising shortcut. Touchard’s congruence says that for any prime p:
Check it with p = 5 and n = 2: B(7) = 877, and 877 = 175·5 + 2, so B(7) ≡ 2. On the other side, B(2) + B(3) = 2 + 5 = 7 ≡ 2 (mod 5). They match. Iterating the congruence bounds the period of the Bell numbers modulo p by (pp − 1)/(p − 1), and for small primes that bound is the exact answer: 13 terms modulo 3, 781 modulo 5, 137,257 modulo 7. Anyone who has stared at modular arithmetic output hunting for a short cycle now knows why none turned up.
Rhyme Schemes, Test Suites, and Equivalence Relations
The cleanest real example is poetry. A rhyme scheme for a four-line stanza is exactly a partition of the four lines into groups that rhyme with each other, so there are B(4) = 15 of them: AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, ABCD. Move to five lines and it is B(5) = 52.
Medieval Japan reached the same 52 from a different direction. In the Genji-kō incense game players burned five sticks and had to say which ones smelled alike — that is a partition of five labelled objects — and the answers were recorded with a set of 52 little diagrams, one per pattern, each named after a chapter of The Tale of Genji. The diagrams are drawn as five vertical strokes with horizontal bars joining the ones that match, which is a set partition written down about seven centuries before Eric Temple Bell put his name on the sequence.
Three more places the sequence turns up with numbers attached:
- Equivalence relations. The number of distinct equivalence relations on an n-element set is B(n), because every equivalence relation is a partition into classes. For a 6-element set that is 203 — not 236, which is the number of arbitrary relations.
- Database and clustering enumeration. Searching every possible clustering of 15 data points means examining B(15) = 1,382,958,545 candidates. That single number is why k-means fixes k in advance and settles for a local optimum instead of an exhaustive search.
- Test-case grouping. Deciding which of 8 configuration flags must be tested together gives B(8) = 4,140 possible groupings — small enough to enumerate, large enough that nobody should do it by hand.
The sequence is catalogued as OEIS A000110, which is the fastest way to check a row you computed yourself, and the standard reference on Bell numbers collects the identities in one place.
Three Counts People Reach For Instead of B(n)
Most wrong answers here are not arithmetic slips — they are the wrong count entirely. Before trusting B(n), check your problem against these:
| If the question is… | You want | At n = 5 |
|---|---|---|
| Split n distinct items into any number of unnamed groups | B(n) | 52 |
| …into exactly k groups | S(n,k) | 25 for k = 3 |
| …into groups that are ranked or named | ordered Bell a(n) | 541 |
| Split the number n into positive summands | integer partitions p(n) | 7 |
The last row is the trap that catches the most people. “Partitions of 5” means 7 if you mean 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1, and it means 52 if you mean splitting five distinguishable objects. A Bell number always assumes the items are distinguishable — swap two of them and you get a different partition unless they were already in the same block.
The third row is the other frequent slip. If the groups have names, ranks, or any order at all, multiply through: ordered Bell a(5) = 541 is more than ten times B(5) = 52, because a partition into three blocks becomes 3! = 6 different ordered arrangements. Assigning five tasks to “some teams” is 52; assigning them to Team 1, Team 2 and so on with the number of teams unfixed is 541.
Row two is where Stirling numbers of the second kind take over, and the relationship is worth stating outright: B(n) = Σk S(n,k). The Bell number is the whole row of the Stirling triangle added up. If your problem fixes the number of groups you need one cell; if it leaves the number of groups free you need the total. That single distinction resolves most of the confusion between the two sequences, and both counts sit next to each other in any decent combinatorics reference.
