Table of Contents

• Definition
• Recurrence Relation
• Code
• References

Definition

Bell numbers are a sequence of numbers that are used to count the number of ways to partition a set.

The Bell number for a set of size n is the number of ways to partition the set into non-empty subsets.

Recurrence Relation

The Bell numbers are given by the following recurrence relation:

The first few Bell numbers are:

Code

from math import comb
 
def bell_number(n: int) -> int:
    # Initialize the Bell number for n = 0
    bell = [0 for _ in range(n + 1)]
    bell[0] = 1
 
    for i in range(1, n + 1):
        bell[i] = sum(comb(i-1, k) * bell[k] for k in range(i))
 
    return bell[n]

References

• Bell Numbers