Bell numbers in Python
Last Updated :
12 Apr, 2024
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} }.
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, ….Â
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:
- Initialize a 2D array
bell
of size (n+1) x (n+1)
and initialize all values as 0. - Initialize
bell[0][0] = 1
. - 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]
.
- 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))
OutputBell 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:
- Initialize a 1D array
bell
of size n+1
and initialize all values as 0. - Initialize
bell[0] = 1
. - 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]
.
- 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))
Time Complexity:Â O(N2)Â
Auxiliary Space:Â O(N)Â
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...