Bell Numbers (Number of ways to Partition a Set)
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} }.
Recommended practice
The solution to above questions is Bell Number.
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.
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 of S(n, k).
Below is Dynamic Programming based implementation of the above recursive code using the Stirling number-
C++
#include <iostream> using namespace std; int main() { int n=5; int s[n+1][n+1]; for ( int i=0;i<n+1;i++){ for ( int j=0;j<n+1;j++){ if (j>i) s[i][j]=0; else if (i==j) s[i][j]=1; else if (i==0 || j==0) s[i][j]=0; else { s[i][j]= j*s[i-1][j] + s[i-1][j-1]; } } } int ans=0; for ( int i=0;i<n+1;i++){ ans += s[n][i]; } cout<<ans; return 0; } |
Java
/*package whatever //do not write package name here */ // Java program to find number of ways of partitioning it. import java.io.*; // "static void main" must be defined in a public class. public class GFG { public static void main(String[] args) { int n = 5 ; int [][] s = new int [n + 1 ][n + 1 ]; for ( int i = 0 ; i < n + 1 ; i++) { for ( int j = 0 ; j < n + 1 ; j++) { if (j > i) s[i][j] = 0 ; else if (i == j) s[i][j] = 1 ; else if (i == 0 || j == 0 ) s[i][j] = 0 ; else { s[i][j] = j * s[i - 1 ][j] + s[i - 1 ][j - 1 ]; } } } int ans = 0 ; for ( int i = 0 ; i < n + 1 ; i++) { ans += s[n][i]; } System.out.println(ans); } } // The code is contributed by Gautam goel (gautamgoel962) |
Python3
# python program to find number of ways of partitioning it. n = 5 s = [[ 0 for _ in range (n + 1 )] for _ in range (n + 1 )] for i in range (n + 1 ): for j in range (n + 1 ): if j > i: continue elif (i = = j): s[i][j] = 1 elif (i = = 0 or j = = 0 ): s[i][j] = 0 else : s[i][j] = j * s[i - 1 ][j] + s[i - 1 ][j - 1 ] ans = 0 for i in range ( 0 ,n + 1 ): ans + = s[n][i] print (ans) |
C#
// C# Program to find number of ways of partitioning it. using System; public class Program { static public void Main( string [] args) { int n = 5; int [, ] s = new int [n + 1, n + 1]; for ( int i = 0; i < n + 1; i++) { for ( int j = 0; j < n + 1; j++) { if (j > i) s[i, j] = 0; else if (i == j) s[i, j] = 1; else if (i == 0 || j == 0) s[i, j] = 0; else s[i, j] = j * s[i - 1, j] + s[i - 1, j - 1]; } } int ans = 0; for ( int i = 0; i < n + 1; i++) ans += s[n, i]; Console.WriteLine(ans); } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
// JavaScript program to find number of ways of partitioning it. let n=5; let s = new Array(n+1); for (let i=0;i<n+1;i++){ s[i] = new Array(n+1); for (let j=0;j<n+1;j++){ if (j>i) s[i][j]=0; else if (i==j) s[i][j]=1; else if (i==0 || j==0) s[i][j]=0; else { s[i][j]= j*s[i-1][j] + s[i-1][j-1]; } } } let ans=0; for (let i=0;i<n+1;i++){ ans += s[n][i]; } console.log(ans) // The code is contributed by Gautam goel (gautamgoel962) |
Output
52
Time complexity: O(N2)
Auxiliary Space: O(N2)
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)
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.
C++14
// 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; } |
Java
// Java program to find n'th Bell number import java.io.*; class GFG { // Function to find n'th Bell Number static int bellNumber( int n) { int [][] bell = new int [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 public static void main (String[] args) { for ( int n= 0 ; n<= 5 ; n++) System.out.println( "Bell Number " + n + " is " +bellNumber(n)); } } // This code is contributed by Pramod Kumar |
Python3
# A Python program to find n'th Bell number def bellNumber(n): bell = [[ 0 for i in range (n + 1 )] for j in range (n + 1 )] bell[ 0 ][ 0 ] = 1 for i in range ( 1 , n + 1 ): # Explicitly fill for j = 0 bell[i][ 0 ] = bell[i - 1 ][i - 1 ] # Fill for remaining values of j for j in range ( 1 , i + 1 ): bell[i][j] = bell[i - 1 ][j - 1 ] + bell[i][j - 1 ] return bell[n][ 0 ] # Driver program for n in range ( 6 ): print ( 'Bell Number' , n, 'is' , bellNumber(n)) # This code is contributed by Soumen Ghosh |
C#
// C# program to find n'th Bell number using System; class GFG { // Function to find n'th // Bell Number static int bellNumber( int n) { int [,] bell = new int [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 Code public static void Main () { for ( int n = 0; n <= 5; n++) Console.WriteLine( "Bell Number " + n + " is " +bellNumber(n)); } } // This code is contributed by nitin mittal. |
Javascript
<script> // Javascript program to find n'th Bell number // Function to find n'th Bell Number function bellNumber(n) { let bell = new Array(n+1); for (let i = 0; i < n + 1; i++) { bell[i] = new Array(n + 1); } bell[0][0] = 1; for (let 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 (let j=1; j<=i; j++) bell[i][j] = bell[i-1][j-1] + bell[i][j-1]; } return bell[n][0]; } for (let n=0; n<=5; n++) document.write( "Bell Number " + n + " is " +bellNumber(n) + "</br>" ); </script> |
PHP
<?php // A PHP program to find // n'th Bell number // function that returns // n'th bell number function bellNumber( $n ) { $bell [0][0] = 1; for ( $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 ( $j = 1; $j <= $i ; $j ++) $bell [ $i ][ $j ] = $bell [ $i - 1][ $j - 1] + $bell [ $i ][ $j - 1]; } return $bell [ $n ][0]; } // Driver Code for ( $n = 0; $n <= 5; $n ++) echo ( "Bell Number " . $n . " is " . bellNumber( $n ) . "\n" ); // This code is contributed by Ajit. ?> |
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: O(N2)
Auxiliary Space: O(N2)
Space Optimized DP Approach:
We can use a 1-D list to represent the previous row of the Bell triangle. We initialize dp[0] to 1, since there is only one way to partition an empty set.
To compute the Bell numbers for n > 0, we first set dp[0] = dp[i-1], since the first element in each row is the same as the last element in the previous row. Then, we use the recurrence relation dp[j] = prev + dp[j-1] to compute the Bell number for each partition, where prev is the value of dp[j] in the previous iteration of the inner loop. We update prev to the temporary variable temp before updating dp[j].
Finally, we return dp[0], which is the Bell number for the partition of a set with n elements into non-empty subsets.
C++
#include <iostream> #include <vector> // Function to calculate the Bell number for 'n' int bellNumbers( int n) { // Initialize the previous row of the Bell triangle with // dp[0] = 1 std::vector< int > dp(n + 1, 0); dp[0] = 1; for ( int i = 1; i <= n; i++) { // The first element in each row is the same as the // last element in the previous row int prev = dp[0]; dp[0] = dp[i - 1]; for ( int j = 1; j <= i; j++) { // The Bell number for n is the sum of the Bell // numbers for all previous partitions int temp = dp[j]; dp[j] = prev + dp[j - 1]; prev = temp; } } return dp[0]; } int main() { int n = 5; std::cout << bellNumbers(n) << std::endl; return 0; } |
Java
import java.util.Arrays; public class BellNumbers { // Function to calculate the Bell number for 'n' static int bellNumbers( int n) { // Initialize the previous row of the Bell triangle // with dp[0] = 1 int [] dp = new int [n + 1 ]; Arrays.fill(dp, 0 ); dp[ 0 ] = 1 ; for ( int i = 1 ; i <= n; i++) { // The first element in each row is the same as // the last element in the previous row int prev = dp[ 0 ]; dp[ 0 ] = dp[i - 1 ]; for ( int j = 1 ; j <= i; j++) { // The Bell number for n is the sum of the // Bell numbers for all previous partitions int temp = dp[j]; dp[j] = prev + dp[j - 1 ]; prev = temp; } } return dp[ 0 ]; } public static void main(String[] args) { int n = 5 ; System.out.println(bellNumbers(n)); } } |
Python3
def bell_numbers(n): # Initialize the previous row of the Bell triangle with dp[0] = 1 dp = [ 1 ] + [ 0 ] * n for i in range ( 1 , n + 1 ): # The first element in each row is the same as the last element in the previous row prev = dp[ 0 ] dp[ 0 ] = dp[i - 1 ] for j in range ( 1 , i + 1 ): # The Bell number for n is the sum of the Bell numbers for all previous partitions temp = dp[j] dp[j] = prev + dp[j - 1 ] prev = temp return dp[ 0 ] n = 5 print (bell_numbers(n)) |
C#
using System; class Program { // Function to calculate the Bell number for 'n' static int BellNumbers( int n) { // Initialize the previous row of the Bell triangle // with dp[0] = 1 int [] dp = new int [n + 1]; dp[0] = 1; for ( int i = 1; i <= n; i++) { // The first element in each row is the same as // the last element in the previous row int prev = dp[0]; dp[0] = dp[i - 1]; for ( int j = 1; j <= i; j++) { // The Bell number for n is the sum of the // Bell numbers for all previous partitions int temp = dp[j]; dp[j] = prev + dp[j - 1]; prev = temp; } } return dp[0]; } static void Main() { int n = 5; Console.WriteLine(BellNumbers(n)); } } |
Javascript
function bellNumbers(n) { // Create an array to store intermediate values, initialized with zeros let dp = new Array(n + 1).fill(0); // The first element represents the Bell number for 0, which is 1 dp[0] = 1; // Iterate through each row of the Bell triangle up to 'n' for (let i = 1; i <= n; i++) { // Store the value of the first element in the current row let prev = dp[0]; // Update the first element of the row using the last element of the previous row dp[0] = dp[i - 1]; // Iterate through each element in the current row for (let j = 1; j <= i; j++) { // Store the current value of dp[j] in a temporary variable let temp = dp[j]; // Update dp[j] by adding the previous value (prev) and the value at dp[j-1] dp[j] = prev + dp[j - 1]; // Update the 'prev' variable for the next iteration of the inner loop prev = temp; } } // Return the Bell number for 'n' return dp[0]; } // Test the function with n = 5 let n = 5; console.log(bellNumbers(n)); |
Output
52
Time Complexity:
Auxiliary Space:
We will soon be discussing other more efficient methods of computing Bell Numbers.
Another problem that can be solved by Bell Numbers.
A number is squarefree if it is not divisible by a perfect square other than 1. For example, 6 is a square free number but 12 is not as it is divisible by 4.
Given a squarefree number x, find the number of different multiplicative partitions of x. The number of multiplicative partitions is Bell(n) where n is number of prime factors of x. For example x = 30, there are 3 prime factors of 2, 3 and 5. So the answer is Bell(3) which is 5. The 5 partitions are 1 x 30, 2 x15, 3 x 10, 5 x 6 and 2 x 3 x 5.
Exercise:
The above implementation causes arithmetic overflow for slightly larger values of n. Extend the above program so that results are computed under modulo 1000000007 to avoid overflows.
Reference:
https://en.wikipedia.org/wiki/Bell_number
https://en.wikipedia.org/wiki/Bell_triangle
This article is contributed by Rajeev Agrawal.