Bell Numbers

Why Bell Numbers Matters

Three distinct people can form any number of nonempty, unnamed teams in five ways: everyone together; one of the three possible pairs with the remaining person alone; or everyone alone. Unlike a query that fixes the number of teams, this question counts every possible set partition.

The Bell number B(n) counts the ways to partition n distinct objects into nonempty, unlabeled blocks. It measures the size of an unrestricted grouping space: possible teams, candidate clusterings, equivalence relations, or patterns of equal and unequal values among positions. It counts configurations; it does not decide which grouping is useful or optimal.

This lesson builds Bell numbers using Bell's triangle, an addition-only dynamic programming method. You will understand its first and last columns, trace every addition through B(4) = 15, implement the same algorithm in Python, C++, and Java, and distinguish full integer counts from modular remainders.

Core Concepts and Terminology

A set partition is a collection of disjoint nonempty blocks whose union is the original set. The objects are distinct, but the blocks have no names. Reordering the blocks or reordering elements within a block does not create a new partition. For example, {1, 2} | {3} and {3} | {2, 1} are identical partitions.

The input is a nonnegative integer n. The output B(n) counts partitions of an n-element labeled set, without specifying the number of blocks. The sequence begins 1, 1, 2, 5, 15, 52, 203, 877, 4140 for n = 0 through 8. There is one empty partition, so B(0) = 1. For n > 0, every counted partition has between one and n blocks.

Stirling numbers separate these partitions by block count: S(n, k) counts those with exactly k blocks. Adding every entry in a second-kind Stirling row gives B(n). For n = 3, the contributions are S(3, 1) = 1, S(3, 2) = 3, and S(3, 3) = 1, totaling five.

Bell's triangle uses a different table. Row 0 is [1]. Each new row begins with the last entry of the previous row. Each subsequent entry is the new entry immediately to its left plus the previous-row entry one column to its left. With rows numbered from zero, row r begins with B(r) and ends with B(r + 1). These intermediate triangle entries are not the counts for fixed numbers of blocks.

How Bell Numbers Works, Step by Step

Initialize previous = [1] and bells = [1]. The first array holds Bell triangle row 0; the second holds the Bell-number prefix, beginning with B(0).

For each row r from 1 through n, start a new array current with current[0] = previous[-1], the previous row's last entry. Then visit columns j = 1 through r from left to right, setting current[j] = current[j − 1] + previous[j − 1]. Append current[0] to bells, replace previous with current, and continue. At termination, bells contains B(0) through B(n).

This update deliberately combines a new-row value on the left with an old-row value above-left. Separate arrays make those roles explicit. The direction differs from one-array Pascal or Stirling updates: the new left neighbor is required here, so it must already have been computed.

For example, to build row 4 from previous = [5, 7, 10, 15], start current = [15]. Column 1 becomes 15 + 5 = 20. Column 2 becomes 20 + 7 = 27. Column 3 becomes 27 + 10 = 37. Column 4 becomes 37 + 15 = 52. The row is [15, 20, 27, 37, 52], so B(4) = 15. Its final entry 52 is the next Bell number, B(5).

The programs reduce every sum modulo M = 1,000,000,007. The triangle rules remain valid for residues because they use only addition. The small diagrams show the full integer values.

flowchart TD
    A["Read n"] --> B{"n negative?"}
    B -->|Yes| X["Reject input"]
    B -->|No| C["previous = [1]; bells = [1]; r = 1"]
    C --> D{"r at most n?"}
    D -->|No| R["Return bells: B(0) through B(n)"]
    D -->|Yes| E["current[0] = last entry of previous; j = 1"]
    E --> F{"j at most r?"}
    F -->|Yes| G["current[j] = (current[j - 1] + previous[j - 1]) mod M"]
    G --> H["j = j + 1"]
    H --> F
    F -->|No| I["Append current[0] to bells"]
    I --> J["previous = current; r = r + 1"]
    J --> D

Worked Example with a Full Trace

Compute the prefix through B(4). Start with triangle row 0, [1], and Bell prefix [1]. For each subsequent row, copy the previous last entry first, then perform the additions in order.

1. Row r = 1: previous = [1]. Seed current[0] = 1. For j = 1, add current[0] + previous[0] = 1 + 1 = 2. The completed row is [1, 2]. Record B(1) = 1; bells becomes [1, 1].
2. Row r = 2: previous = [1, 2]. Seed current[0] = 2. For j = 1, 2 + 1 = 3. For j = 2, 3 + 2 = 5. The completed row is [2, 3, 5]. Record B(2) = 2; bells becomes [1, 1, 2].
3. Row r = 3: previous = [2, 3, 5]. Seed current[0] = 5. For j = 1, 5 + 2 = 7. For j = 2, 7 + 3 = 10. For j = 3, 10 + 5 = 15. The completed row is [5, 7, 10, 15]. Record B(3) = 5; bells becomes [1, 1, 2, 5].
4. Row r = 4: previous = [5, 7, 10, 15]. Seed current[0] = 15. For j = 1, 15 + 5 = 20. For j = 2, 20 + 7 = 27. For j = 3, 27 + 10 = 37. For j = 4, 37 + 15 = 52. The completed row is [15, 20, 27, 37, 52]. Record B(4) = 15; bells becomes [1, 1, 2, 5, 15].

There are ten additions across rows 1 through 4. The required answer is 15, read from the first entry of row 4. The final entry 52 belongs to B(5), even though we did not request B(5) in this run.

An independent counting check singles out element 4 in a partition of {1, 2, 3, 4}. Choose the other members of its block from the first three elements, then partition whatever remains. With zero, one, two, or three companions, the counts are 5, 3 × 2, 3 × 1, and 1. Their sum is 5 + 6 + 3 + 1 = 15.

Implementation in Python, C++, and Java

Every panel is a complete standalone program. The function returns Bell numbers from B(0) through B(n), reduced modulo M = 1,000,000,007. The sample programs compute the prefix through 20 once, then print the same selected entries. The values through B(10) shown here are full counts; the B(15) and B(20) lines are remainders.

Python uses arbitrary-precision integers. C++ uses long long; every stored residue is below M, so every sum is at most 2M − 2 = 2,000,000,012 and fits safely. Java uses BigInteger addition and explicit modular reduction. No factorials, floating-point approximations, multiplication of counts, or modular division are required.

All versions reject negative n. C++ and Java accept a signed 32-bit n, with actual feasible sizes limited by memory and quadratic work. Separate previous/current arrays preserve the old row while the new row is built from left to right. Only two triangle rows are retained, together with the requested Bell prefix.

MOD = 1_000_000_007


def bell_numbers(n: int) -> list[int]:
    if n < 0:
        raise ValueError("n must be nonnegative")
    previous = [1]
    bells = [1]
    for row in range(1, n + 1):
        current = [previous[-1]]
        for j in range(1, row + 1):
            current.append((current[j - 1] + previous[j - 1]) % MOD)
        bells.append(current[0])
        previous = current
    return bells


def main() -> None:
    samples = [0, 1, 2, 3, 4, 5, 10, 15, 20]
    bells = bell_numbers(max(samples))
    print(f"modulus = {MOD}")
    for n in samples:
        print(f"B({n}) = {bells[n]}")


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <vector>

constexpr long long MOD = 1'000'000'007LL;

std::vector<long long> bell_numbers(int n) {
    if (n < 0) {
        throw std::invalid_argument("n must be nonnegative");
    }
    std::vector<long long> bells(static_cast<std::size_t>(n) + 1, 0);
    bells[0] = 1;
    std::vector<long long> previous = {1};
    for (std::size_t row = 1; row < bells.size(); ++row) {
        std::vector<long long> current(row + 1, 0);
        current[0] = previous.back();
        for (std::size_t j = 1; j <= row; ++j) {
            current[j] = (current[j - 1] + previous[j - 1]) % MOD;
        }
        bells[row] = current[0];
        previous.swap(current);
    }
    return bells;
}

int main() {
    const std::vector<int> samples = {0, 1, 2, 3, 4, 5, 10, 15, 20};
    const int maximum = *std::max_element(samples.begin(), samples.end());
    const std::vector<long long> bells = bell_numbers(maximum);
    std::cout << "modulus = " << MOD << '\n';
    for (int n : samples) {
        std::cout << "B(" << n << ") = " << bells[n] << '\n';
    }
}

import java.math.BigInteger;

public class Main {
    private static final BigInteger MOD = BigInteger.valueOf(1_000_000_007L);

    public static BigInteger[] bellNumbers(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be nonnegative");
        }
        BigInteger[] bells = new BigInteger[Math.addExact(n, 1)];
        bells[0] = BigInteger.ONE;
        BigInteger[] previous = {BigInteger.ONE};
        for (int row = 1; row < bells.length; ++row) {
            BigInteger[] current = new BigInteger[Math.addExact(row, 1)];
            current[0] = previous[previous.length - 1];
            for (int j = 1; j <= row; ++j) {
                current[j] = current[j - 1].add(previous[j - 1]).mod(MOD);
            }
            bells[row] = current[0];
            previous = current;
        }
        return bells;
    }

    public static void main(String[] args) {
        int[] samples = {0, 1, 2, 3, 4, 5, 10, 15, 20};
        int maximum = 0;
        for (int n : samples) {
            maximum = Math.max(maximum, n);
        }
        BigInteger[] bells = bellNumbers(maximum);
        System.out.println("modulus = " + MOD);
        for (int n : samples) {
            System.out.println("B(" + n + ") = " + bells[n]);
        }
    }
}

Run Python with Python 3.9 or later. Compile C++ with C++14 or later. Save Java as Main.java, compile with javac Main.java, and run with java Main. Each program prints the following ten lines:

• modulus = 1000000007
• B(0) = 1
• B(1) = 1
• B(2) = 2
• B(3) = 5
• B(4) = 15
• B(5) = 52
• B(10) = 115975
• B(15) = 382958538
• B(20) = 157873304

The full values are B(15) = 1,382,958,545 and B(20) = 51,724,158,235,372. Their residues are the two large-index outputs above. To obtain full counts in Python or Java, remove modular reduction while retaining arbitrary-precision integers. C++ needs arbitrary-precision arithmetic or a proven bound on every triangle entry, including the last entry of row n, which is B(n + 1). Merely checking whether the requested B(n) fits is not enough for this implementation.

Complexity, Correctness, and Invariants

For n ≥ 1, row r performs r additions. The total is 1 + 2 + … + n = n(n + 1)/2, so the algorithm takes Θ(n²) time under fixed-modulus, unit-cost arithmetic. The previous row, current row, and Bell prefix each have O(n) entries at peak, giving Θ(n + 1) total storage. The auxiliary storage remains O(n) even if the returned prefix is excluded from the accounting. For n = 0, time and storage are Θ(1).

For a fixed n, best, average, and worst cases have the same loop count; there is no data-dependent branching in the triangle construction. Negative input is rejected before allocation. The space bound refers to a live pair of rows, not every row ever allocated. If full integer counts are required, growing operand sizes make addition nonconstant in bit operations; the precise bit cost depends on their lengths.

To prove the triangle's meaning, let T(r, j) count partitions of {1, …, r + 1} in which the distinguished element r + 1 may share a block only with elements from {1, …, j}. When j = 0, the distinguished element must be alone, leaving any partition of the other r objects, so T(r, 0) = B(r). When j = r, every possible companion is allowed, so T(r, r) = B(r + 1).

For j ≥ 1, split the counted partitions into two cases. If j does not share the distinguished block, the count is T(r, j − 1). If j does share it, delete j from that block. The distinguished element stays, so the block does not disappear; after relabeling, the remaining partition is counted by T(r − 1, j − 1). Inserting j back into the distinguished block reverses this operation uniquely. Therefore T(r, j) = T(r, j − 1) + T(r − 1, j − 1), exactly the triangle update.

The algorithm starts with T(0, 0) = 1. Copying the previous row's final entry gives current[0] = T(r − 1, r − 1) = B(r), the correct new boundary. Before computing column j, the current prefix through j − 1 is correct and the previous row is unchanged; the recurrence therefore produces the correct next entry. Row induction proves every first-column Bell value. Reducing additions modulo M preserves the same argument for residues.

The binomial alternative uses B(n + 1) = sum over j = 0…n of binomial(n, j) × B(n − j). Choose j companions for a distinguished new object, then partition the remaining objects. The same identity provides a convenient independent reference implementation. As with the triangle, arithmetic-operation counts must be distinguished from bit costs when using full counts.

Variants, Pitfalls, and Optimizations

Keep Bell and Stirling questions separate. B(n) counts all block counts, while S(n, k) fixes k. Partitions into at most k blocks number the sum of S(n, j) for j = 0…min(n, k). Named destinations are a different model: onto assignments to k labeled destinations number k! × S(n, k), and assignments allowing empty destinations number kⁿ. Bell numbers do not label their blocks.

Read the correct triangle boundary. With row zero equal to [1], the first entry of row r is B(r), and the last is B(r + 1). The last entry becomes the next row's first entry. Copying the previous first entry instead of its last value changes the table. Also avoid adding a zero boundary as though this were Pascal's triangle: the seeding rule is different.

Do not overwrite values you still need. The current row is built left to right because each entry depends on its new left neighbor. The previous row must stay intact until the row is finished. A one-array implementation is possible if old values are saved carefully, but two arrays make the invariant easier to inspect without changing the asymptotic storage.

Choose whether to count, enumerate, or constrain. If only B(n) is needed, the prefix output array can be omitted, although the two triangle rows still use O(n) storage. If every partition is needed, use a canonical generator such as a restricted-growth representation, where each new block receives the next unused label. If block sizes are constrained, unrestricted Bell numbers no longer apply.

For example, let F(n) count partitions whose block sizes are at most b. Fix one distinguished object and choose the rest of its block: F(0) = 1 and F(n) is the sum, over s = 1…min(b, n), of binomial(n − 1, s − 1) × F(n − s). The block containing the distinguished object has size s, and the remaining n − s objects form any permitted partition. A similar restriction to allowed sizes can exclude singletons.

Use richer counting tools only when needed. The weighted polynomial Pₙ(t) = sum over k of S(n, k)tᵏ records partitions by block count, and Pₙ(1) = B(n). The exponential generating function is sum over n of B(n)xⁿ/n! = exp(exp(x) − 1): a partition is a set of nonempty labeled blocks. These identities explain additional structure, while the triangle remains a direct addition-only computation.

Practice Problems and Real-World Use

Before applying Bell numbers, verify that the objects are distinct, every block is nonempty, blocks are unlabeled, and the number of blocks is unrestricted. If any of these assumptions changes, identify the modified counting problem before choosing a recurrence.

Bell numbers are useful when assessing how many groupings a search or test generator might need to consider. They do not supply a clustering objective, enforce capacities, or enumerate outputs automatically. Canonical representations prevent a grouping from being counted again merely because its blocks are written in a different order.

For equality patterns, the digits are canonical block labels, not fixed values from a binary alphabet: pattern 012 uses three distinct values. Label each block by its order of first appearance. This gives one representation per partition and avoids counting permutations of value names separately.

For the graph example, singleton blocks become isolated vertices. Conversely, each connected component of a graph whose components are cliques gives one block. These two constructions reverse one another, so the number of graphs is the Bell number for the labeled vertex set.

Validate the programs in several independent ways: compare small outputs with a canonical partition generator; sum second-kind Stirling rows; and use the binomial Bell recurrence. Include n = 0, negative-input rejection, B(3) = 5 versus the next diagonal value 15, and indices such as 15 or 20 where modular reduction changes the displayed value. Those checks exercise the counting model, row indexing, recurrence, and arithmetic together.