Bell Number in Java
The Bell number is a sequence of numbers that counts the number of ways to partition a set. It is named after Eric Temple Bell, a renowned mathematician. In Java, you can calculate the Bell number using various approaches, such as using a recursive method or using dynamic programming. I will explain the dynamic programming approach and also using the recursive method.
Example 1
In the given code, the calculateBellNumber method takes an integer n as input and calculates the Bell number for that value using dynamic programming. The Bell triangle is represented by the 2D array bell, where bell[i][j] represents the Bell number for i and j values.
FileName: BellNumber.java
public class BellNumber { public static int calculateBellNumber(int n) { // Create a 2D array to store the Bell numbers int[][] bell = new int[n + 1][n + 1]; bell[0][0] = 1; // Calculate the Bell numbers using dynamic programming for (int i = 1; i <= n; i++) { // Initialize the first element of each row with the last element of the previous row bell[i][0] = bell[i - 1][i - 1]; for (int j = 1; j <= i; j++) { // Calculate the Bell number using the values from the previous row and column bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1]; } } // Return the Bell number for n return bell[n][0]; } public static void main(String[] args) { // Set the value of n int n = 7; // Calculate the Bell number for n int bellNumber = calculateBellNumber(n); // Display the result System.out.println("Bell number for n = " + n + " is " + bellNumber); } }
Output
Bell number for n = 7 is 877
Example 2
The given Java code implementation of the dynamic programming approach to calculate the Bell numbers. It prints the Bell numbers for n values from 0 to 10.
FileName: BellNumber.java
import java.io.*; public class BellNumber { // Function that finds the nth 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++) { bell[i][0] = bell[i - 1][i - 1]; // Fill the first column of the current row with the value from the previous row's last column for (int j = 1; j <= i; j++) { bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1]; // Calculate the value using the recurrence relation } } return bell[n][0]; // Return the Bell number for the given input n } // Driver program public static void main(String args[]) { for (int n = 0; n <= 10; n++) { System.out.println("Bell Number " + n + " is " + bellNumber(n)); // Print the Bell number for each value of n from 0 to 5 } } }
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 Bell Number 6 is 203 Bell Number 7 is 877 Bell Number 8 is 4140 Bell Number 9 is 21147 Bell Number 10 is 115975
Example 3
In the given code, the bellNumber method is defined to calculate the Bell number using recursion. It serves as the entry point to the recursive calculation. The calculateBellNumberRecursive method is the recursive helper function. It takes two parameters: n and k. It checks for the base cases where n or k becomes 0 and returns the appropriate values. If k is 1, it calls bellNumber(n - 1) to calculate the Bell number for n - 1. Otherwise, it recursively calculates the Bell number by summing up the results of two recursive calls with updated values of n and k.
FileName: BellNumber.java
public class BellNumber { // Recursive method to calculate the Bell number static int bellNumber(int n) { if (n == 0) { return 1; // Base case: Bell number for n = 0 is 1 } else { return calculateBellNumberRecursive(n, n); // Call the recursive helper function } } // Recursive helper function to calculate the Bell number static int calculateBellNumberRecursive(int n, int k) { if (n == 0 || k == 0) { return 0; // Base case: If n or k becomes 0, return 0 } else if (k == 1) { return bellNumber(n - 1); // If k is 1, call bellNumber(n - 1) to calculate Bell number for n - 1 } else { // Recursive case: Calculate Bell number by summing up results of two recursive calls with updated values of n and k return calculateBellNumberRecursive(n, k - 1) + calculateBellNumberRecursive(n - 1, k - 1); } } public static void main(String[] args) { for (int n = 0; n <= 10; n++) { System.out.println("Bell Number " + n + " is " + bellNumber(n)); // Print the Bell number for each value of n from 0 to 5 } } }
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 Bell Number 6 is 203 Bell Number 7 is 877 Bell Number 8 is 4140 Bell Number 9 is 21147 Bell Number 10 is 115975