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

← Prev Next →