Mathwords logoMathwords

Bell Number — Definition, Formula & Examples

A Bell number counts the total number of ways to partition a set of nn elements into non-empty, non-overlapping subsets. For example, the Bell number B3=5B_3 = 5 means there are exactly 5 ways to partition a 3-element set.

The nn-th Bell number BnB_n is defined as the sum of Stirling numbers of the second kind over all possible block counts: Bn=∑k=0nS(n,k)B_n = \sum_{k=0}^{n} S(n,k), where S(n,k)S(n,k) counts the number of partitions of an nn-element set into exactly kk non-empty subsets. By convention, B0=1B_0 = 1.

Key Formula

Bn=∑k=0nS(n,k)B_{n} = \sum_{k=0}^{n} S(n,k)
Where:
  • BnB_n = The $n$-th Bell number, counting all partitions of an $n$-element set
  • S(n,k)S(n,k) = Stirling number of the second kind — the number of partitions of $n$ elements into exactly $k$ non-empty subsets

How It Works

You can compute Bell numbers using the Bell triangle (analogous to Pascal's triangle). Start by placing B0=1B_0 = 1 at the top. Each subsequent row begins with the last element of the previous row, and each following entry is the sum of the entry to its left and the entry directly above that left entry. The first element of each row gives the next Bell number. The sequence begins 1,1,2,5,15,52,203,…1, 1, 2, 5, 15, 52, 203, \ldots

Worked Example

Problem: Find B4B_4, the number of ways to partition the set {a,b,c,d}\{a, b, c, d\} into non-empty subsets.
Step 1: Compute each Stirling number S(4,k)S(4,k) for k=0k = 0 to 44.
S(4,0)=0,  S(4,1)=1,  S(4,2)=7,  S(4,3)=6,  S(4,4)=1S(4,0)=0,\; S(4,1)=1,\; S(4,2)=7,\; S(4,3)=6,\; S(4,4)=1
Step 2: Sum all Stirling numbers to get the Bell number.
B4=0+1+7+6+1=15B_4 = 0 + 1 + 7 + 6 + 1 = 15
Step 3: Verify by listing partition types: 1 way with one block ({a,b,c,d}\{a,b,c,d\}), 7 ways with two blocks, 6 ways with three blocks, and 1 way with four singletons.
Answer: B4=15B_4 = 15. There are 15 distinct partitions of a 4-element set.

Visualization

Why It Matters

Bell numbers appear in database theory when counting the number of ways to group query results, in clustering algorithms that evaluate all possible groupings, and in coding theory. They are a standard topic in discrete mathematics and combinatorics courses at the undergraduate level.

Common Mistakes

Mistake: Confusing Bell numbers with Stirling numbers of the second kind.
Correction: S(n,k)S(n,k) counts partitions into exactly kk blocks, while BnB_n sums over all possible values of kk. The Bell number is the total count across all block sizes.