# Program for nth Catalan Number (using BigInteger in JAVA)

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