1. Bell Numbers

1.1. Introduction

Bell numbers is the number of ways to partition a set. Given a set of $n$ elements, find number of ways of partitioning it.

Examples:

# Example 1
Input:  n = 2
Output: Number of ways = 2
Explanation: Let the set be {1, 2}
            { {1}, {2} } 
            { {1, 2} }

# Example 2
Input:  n = 3
Output: Number of ways = 5
Explanation: Let the set be {1, 2, 3}
             { {1}, {2}, {3} }
             { {1}, {2, 3} }
             { {2}, {1, 3} }
             { {3}, {1, 2} }
             { {1, 2, 3} }.

The solution to above questions is Bell Number.

1.2. What is a Bell Number?

Let $S (n, k)$ be total number of partitions of $n$ elements into $k$ sets. The value of n’th Bell Number is sum of $S (n, k)$ for k = 1 to n. $B e l l (n) = n \sum k = 1 S (n, k)$ Value of $S (n, k)$ can be defined recursively as $(n + 1, k) = k * S (n, k) + S (n, k - 1)$

1.3. How does above recursive formula work?

When we add a (n+1)’th element to k partitions, there are two possibilities. 1) It is added as a single element set to existing partitions, i.e, S(n, k-1) 2) It is added to all sets of every partition, i.e., k*S(n, k) $S (n, k)$ is called Stirling numbers of the second kind First few Bell numbers are 1, 1, 2, 5, 15, 52, 203, ….

A Simple Method to compute n’th Bell Number is to one by one compute $S (n, k)$ for $k$ = 1 to $n$ and return sum of all computed values. Refer this for computation $o f S (n, k)$ . Below is Dynamic Programming based implementation of the above recursive code using the Stirling number-

1.4. Bell Triangle

A Better Method is to use Bell Triangle. Below is a sample Bell Triangle for first few Bell Numbers.

1
1 2
2 3 5
5 7 10 15
15 20 27 37 52

The triangle is constructed using below formula.

// If this is first column of current row 'i'
If j == 0
   // Then copy last entry of previous row
   // Note that i'th row has i entries
   Bell(i, j) = Bell(i-1, i-1) 

// If this is not first column of current row
Else 
   // Then this element is sum of previous element 
   // in current row and the element just above the
   // previous element
   Bell(i, j) = Bell(i-1, j-1) + Bell(i, j-1)

1.4.1. Interpretation

Then Bell(n, k) counts the number of partitions of the set {1, 2, …, n + 1} in which the element k + 1 is the largest element that can be alone in its set. For example, Bell(3, 2) is 3, it is count of number of partitions of {1, 2, 3, 4} in which 3 is the largest singleton element. There are three such partitions:

    {1}, {2, 4}, {3}
    {1, 4}, {2}, {3}
    {1, 2, 4}, {3}.

Below is Dynamic Programming based implementation of above recursive formula.

Bell Numbers