Program for nth Catalan Number (using BigInteger in JAVA)

Software Development
1

Hello Everyone,

Catalan numbers are a sequence of natural numbers that occurs in many interesting counting problems like following.

  1. Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
  2. Count the number of possible Binary Search Trees with n keys
  3. Count the number of full binary trees (A rooted binary tree is full if every vertex has either two children or no children) with n+1 leaves.
  4. Given a number n, return the number of ways you can draw n chords in a circle with 2 x n points such that no 2 chords intersect.

Solution using BigInteger in java:

  • Finding values of catalan numbers for N>80 is not possible even by using long in java, so we use BigInteger

  • Here we find solution using Binomial Coefficient method as discussed above

  • Java

import java.io.*;

import java.util.*;

import java.math.*;

class GFG

{

public static BigInteger findCatalan( int n)

{

// using BigInteger to calculate large factorials

BigInteger b = new BigInteger( "1" );

// calculating n!

for ( int i = 1 ; i <= n; i++) {

b = b.multiply(BigInteger.valueOf(i));

}

// calculating n! * n!

b = b.multiply(b);

BigInteger d = new BigInteger( "1" );

// calculating (2n)!

for ( int i = 1 ; i <= 2 * n; i++) {

d = d.multiply(BigInteger.valueOf(i));

}

// calculating (2n)! / (n! * n!)

BigInteger ans = d.divide(b);

// calculating (2n)! / ((n! * n!) * (n+1))

ans = ans.divide(BigInteger.valueOf(n + 1 ));

return ans;

}

// Driver Code

public static void main(String[] args)

{

int n = 5 ;

System.out.println(findCatalan(n));

}

}

Output

42