Catalan number in Java

In general mathematics, Catalan numbers can be defined as the sequence of natural numbers that frequently occur in counting problems often encountered in recursively defined objects.

Mathematical formula of Catalan number

Coming to the technical aspects of Catalan numbers, we are often asked to find whether a given number is a Catalan number or not. So how do we do that?

For that, we have steps to identify it.

Firstly, in the mathematical formula, assign a positive integer value to the variable n.

Then find the 2nCn ,n value will be any integer taken in step 1.

i.e 2nCn =  (2n!)/((n+1)!n!)

Uses of Catalan number

• Catalan number is applied in finding the no of binary search trees possible with the n keys.
• Also used to find the permutations of 1...n by avoiding a pattern such as 123 or 1234
• And into how many triangles a polygon of n+2 sides can be split by connecting the vertices.
• The number of full btrees.
• First few catalan numbers can be 1,1,2,5,14,42,132,429, 1430....where n can be 0,1,2,3.....

CatlnNumber.java:

class CatlnNumber {
    // this logic serves the procedure for a recursive function to find the nth Catln number
    int Catln (int n)
    {
        int result = 0;
        // Base condition 
        if (n <= 1)
        {
            return 1;
        }
        for (int i = 0; i < n; i++)
        {
            result += Catln(i) * Catln(n - i - 1);
        }
        return result;
    }
    public static void main (String [] args)
    {
        CatlnNumber cn = new CatlnNumber ();
        for (int i = 0; i < 10; i++)
        {
            System.out.print (cn.Catln (i) + " ");
        }
    }
}

Output:

CatlnNumber1.java:

import java.io.*;
import java.util.*;


class CatlnNumber {
 
    // A dynamic programming method or function that can be used to find nth
    // catln number
    static int CatlnDP(int n)
    {
        // store results of subproblems
        int catln[] = new int[n + 2];
 
        // Initialization first two catalan values into the table
        catln[0] = 1;
        catln[1] = 1;
 
        // Filling the entries into catln[]
        // using the recursive formula
        for (int i = 2; i <= n; i++) {
            catln[i] = 0;
            for (int j = 0; j < i; j++) 
           {
                catln[i] += catln[j] * catln[i - j - 1];
            }
        }
 
        // Returning the last entry
        return catln [n];
    }
    public static void main (String [] args)
    {
        Scanner scan = new Scanner (System.in);
        System.out.println("enter the cat");
        int cat=scan.nextInt();
        for (int i = 0; i < cat; i++) 
       {
            System.out.println(CatlnDP(i) + " ");
        }
    }
}

Output:

Using binomial coefficient:

CatlnNumber.java

import java.io.*;
import java.util.*;
class CatlnNumber {
 
    // Returns value of Binomial Coefficient C(n, k)
    static long binoCoeff(int n, int k)
    {
        long result= 1;
 
        // Since C(n, k) = C(n, n-k)
        if (k > n - k) {
            k = n - k;
        }
 
        // Calculating the value of [n*(n-1)*---*(n-k+1)] /
        // [k*(k-1)*---*1]
        for (int i = 0; i < k; ++i) {
            result *= (n - i);
            result /= (i + 1);
        }
 
        return result;
    }
 
    // using the binomial coefficient concept to generate a function 
    //  that finds nth catln number in O(n) time
    static long Catalan (int n)
    {
        // Calculate value of 2nCn
        long c = binoCoeff(2 * n, n);
 
        // return 2nCn/(n+1)
        return c / (n + 1);
    }


    public static void main (String [] args)
    {
        Scanner scan = new Scanner (System.in);
        System.out.println ("enter the cat");
        int cat=scan.nextInt ();


        for (int i = 0; i < cat; i++) {
            System.out.println (catalan(i) + " ");
        }
    }
}

Output:

We can calculate up to 80 Catalan numbers by using the above method. For numbers greater than 80, we prefer using the BigInteger method in Java.

By using Big Integer:

CatlnNumber.java

import java.io.*;
import java.util.*;
import java. math.*;


class CatlnNumber
{
        public static BigInteger CatalnFind(int n)
       {
             // using BigInteger to find out the factorials of larger numbers
              BigInteger big = new BigInteger("1");
                  // calculating factorial of n
             for (int i = 1; i <= n; i++) 
            {
                  big = big.multiply(BigInteger.valueOf(i));
             }
            // n! * n!
            big = big.multiply(big);


           BigInteger de = new BigInteger("1");
           // calculate (2n)!
          for (int i = 1; i <= 2 * n; i++) 
         {
                de = de.multiply(BigInteger.valueOf(i));
}


                // calculate (2n)! / (n! * n!)
               BigInteger answer = de.divide(big);
              // calculate (2n)! / ((n! * n!) * (n+1))
              answer = answer.divide(BigInteger.valueOf(n + 1));
              return answer;
             }
              public static void main (String [] args)
               {
                         Scanner scan = new Scanner (System.in);
                         System.out.println ("enter the nth cat");
                         int cat = scan.nextInt();
                         System.out.println (CatalnFind (cat));    
                  }
}

Output: