Hello Everyone,
Given a set of n elements, find number of ways of partitioning it.
Examples:
Input: n = 2
Output: Number of ways = 2
Explanation: Let the set be {1, 2}
{ {1}, {2} }
{ {1, 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} }.
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.
Value of S(n, k) can be defined recursively as, S(n+1, k) = k*S(n, k) + S(n, k-1)
How does above recursive formula work?
When we add a (n+1)’th element to k partitions, there are two possibilities.
- It is added as a single element set to existing partitions, i.e, S(n, k-1)
- 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.
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)
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.
// A C++ program to find n'th Bell number
#include<iostream>
using namespace std;
int bellNumber( int n)
{
int bell[n+1][n+1];
bell[0][0] = 1;
for ( int i=1; i<=n; i++)
{
// Explicitly fill for j = 0
bell[i][0] = bell[i-1][i-1];
// Fill for remaining values of j
for ( int j=1; j<=i; j++)
bell[i][j] = bell[i-1][j-1] + bell[i][j-1];
}
return bell[n][0];
}
// Driver program
int main()
{
for ( int n=0; n<=5; n++)
cout << "Bell Number " << n << " is "
<< bellNumber(n) << endl;
return 0;
}
Output:
Bell Number 0 is 1 Bell Number 1 is 1 Bell Number 2 is 2 Bell Number 3 is 5 Bell Number 4 is 15 Bell Number 5 is 52
Time Complexity of above solution is O(n2).