Skip to content
Related Articles

Related Articles

Bell Numbers (Number of ways to Partition a Set)

View Discussion
Improve Article
Save Article
  • Difficulty Level : Medium
  • Last Updated : 29 Jun, 2022
View Discussion
Improve Article
Save Article

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

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. 
Bell(n) = \sum_{k=1}^{n}S(n,k)
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 = int(input())
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++




// 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.

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.
?>

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>

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) 

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. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
 


My Personal Notes arrow_drop_up
Recommended Articles
Page :

Start Your Coding Journey Now!