Open In App

Bell numbers in Python

Last Updated : 12 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Given a set of n elements, find the 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. 
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, …. 

Approach: Dynamic Programming to Calculate Bell Numbers

To calculate the Bell number for a given n, we use a dynamic programming approach where we store the previous Bell numbers to calculate the next Bell number.

Steps:

  1. Initialize a 2D array bell of size (n+1) x (n+1) and initialize all values as 0.
  2. Initialize bell[0][0] = 1.
  3. Loop through each row i from 1 to n and each column j from 1 to i:
    • Set bell[i][j] = bell[i-1][j-1] + bell[i][j-1].
  4. Return bell[n][0] as the n-th Bell number.

Code

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))

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) 

Approach: Space-Optimized Dynamic Programming to Calculate Bell Numbers

To optimize the space complexity, we can use a 1D array instead of a 2D array to store the Bell numbers. We only need to store the previous row values to calculate the next row values.

Steps:

  1. Initialize a 1D array bell of size n+1 and initialize all values as 0.
  2. Initialize bell[0] = 1.
  3. Loop through each row i from 1 to n and each column j from 1 to i:
    • Update bell[j] = bell[j-1] + bell[j].
  4. Return bell[n] as the n-th Bell number.

Code

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))

Output
52

Time Complexity: O(N2) 
Auxiliary Space: O(N) 



Like Article
Suggest improvement
Previous
Next
Share your thoughts in the comments

Similar Reads