Bell number

Count the number of ways to partition a set of n labeled elements.

dp combinatorics math partition integer

The Bell number B(n) is the number of ways to partition a set of n distinct elements into non-empty subsets. For example, B(3) = 5 because the set {1, 2, 3} can be partitioned in 5 ways: {{1},{2},{3}}, {{1,2},{3}}, {{1,3},{2}}, {{2,3},{1}}, and {{1,2,3}}.

Implement the function `bell_number(n: int) -> int` that returns B(n).

- The Bell number satisfies the recurrence: B(0) = 1 and B(n) = sum_{k=0}^{n-1} C(n-1, k) * B(k).
- You may use dynamic programming with the Bell triangle (also known as the Aitken's array) or any correct method.
- Input `n` is a non-negative integer.
- Return the exact integer B(n).

Constraints

0 ≤ n ≤ 20. The result fits within a Python int (B(20) = 51724158235372).
Expected time complexity: O(n^2) or better.

Example

>>> bell_number(0)
1
>>> bell_number(1)
1
>>> bell_number(3)
5
>>> bell_number(5)
52

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Start with a triangle where the first entry of each row is the last entry of the previous row.

Each next entry in a row is the sum of the entry above it and the entry to its left.

The Bell number B(n) is the first entry of row n (or the last entry of row n-1) in the triangle.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.