nth Catalan Number in Java

Catalan numbers are used in many mathematical problems. These are a sequence of numbers. The first few Catalan numbers can be given as:
1, 1, 2, 5, 14, 42, 132, 429, 1430, and so on.

In this post, we will discuss the algorithm and their implementation in Java to obtain these numbers.

Recursive Program for Catalan Numbers

The recursive algorithm to obtain Catalan numbers is based on the following formula. The formula is as follows:
C₀ = 1 and C_n+1 = Σⁿ_i=0 C_iC_n-i for n>=0;

The below example program is the implementation of the above formula. Have a good look at the code and try to understand what happens at each step.

import java.io.*; 
class Catalan{
    int catalan(int n)
    {
        if (n == 0 || n == 1)
        {
            return 1;
        }
        
        int cn = 0;
        
        for( int i=0; i<n; i++)
        {
            cn = cn + catalan(i) * catalan(n-i-1);
        }
        return cn;
    }
}

class Example{
    public static void main(String args[]){
        Catalan c = new Catalan();
        for(int i=0; i<10 ; i++)
        {
            System.out.println(c.catalan(i));
        }
    }
}

Output:

1
1
2
5
14
42
132
429
1430
4862

Here, we have created a class Catalan which has a method catalan() that returns Catalan number for a given value of n starting from 0. As you can see, the function catalan() is being called recursively in the program. Hence it is a recursive solution to our problem.

Using Binomial Coefficient

Another formula that we can use to get Catalan numbers can be given as:

C_n = (2n!)/((n+1)!n!)
We will be implementing the above formula in Java using the following program. See the code.

import java.io.*;

class Catalan{
    long fact(int n){
        if (n == 0 || n == 1)
            return 1;
        else
            return n * fact(n-1);
    }
    
    long catalan(int n){
        return (fact(2 * n))/(fact(n+1) * fact(n));
    }
    
}

class Example {
  public static void main (String[] args) {
    Catalan c = new Catalan();
    
    for(int i=0; i<10; i++)
    {
        System.out.println(c.catalan(i));
    }
  }
}

Output:

1
1
2
5
14
42
132
429
1430
4862

In the above program, we have two methods fact() and catalan() in class Catalan. These methods generate factorial and Catalan numbers resepectively. fact() method is used by the catalan() method as given in the formula to get the desired result.

Thank you.

Also read: Calculating factorial using recursion in Java