## Catalan Numbers

Catalan Numbers are a sequence of natural numbers that occur in many combinatorial problems involving branching and recursion. Here's a list of only some of the many problems in combinatorics reduce to finding Catalan numbers:
• Catalan's problem - computing the number of binary bracketings of n tokens.
• Counting boolean associations - Count the number of ways n factors can be completely parenthesized. (Answer is C(n-1))
• Counting well-formed sequences of parentheses - Calculate the number of expressions containing n pairs of parentheses that are correctly matched (Answer is C(n))
• Counting the number of full binary trees with n leaves (Answer is C(n-1)). A full binary tree is one where each node has either 0 or 2 children.
• Counting the number of full binary trees with n nodes (Answer is C(n)). A full binary tree is one where each node has either 0 or 2 children.
• Euler's Polygon Division Problem - Figure out how many ways you can diagonally cut a polygon into triangles. (Equivalent to counting polygon triangulations). The answer is C(n-2)
• Counting the number of monotonic paths through a grid with size n x n. The answer is C(n). This problem is often used as a visual example to teach both Catalan numbers and dynamic programming.
• Counting the number of ways to create a stairstep shaped area of height n with n rectangles. The answer is C(n).
• Counting the number of ways to make handshakes without crossing hands.
• Counting the number of "mountain ranges" you can draw with n upstrokes and n downstrokes. (Related to monotonic paths problem listed above)

Catalan numbers are given by the following closed-form equations: However, the equations above require computation of binomial coefficients or factorials. An alternative way to compute Catalan numbers is through its recurrence relations: Which can be done with Dynamic Programming. However, Catalan Numbers also go by this recurrence relation that is even easier to compute iteratively: // Author: Christopher Vo
// Various ways of computing the Catalan Numbers
// Direct method (fastest): catalan(n)
// Using Factorial (slow): catalan_fact(n)
// Using Binomial Coefficients (slowest): catalan_binom(n)
import java.math.BigInteger;
public class NumberTests {

/* Compute factorial iteratively */
public static BigInteger fact(int n) {
BigInteger num = BigInteger.ONE;
for (int i = 1; i <= n; i++)
num = num.multiply(BigInteger.valueOf(i));
return num;
}

/* Compute binomial coefficient (n choose m) using DP (with BigInteger) */
public static BigInteger binomial(int n, int m) {
int i, j;
BigInteger[] b = new BigInteger[n + 1];
b = BigInteger.ONE;
for (i = 1; i <= n; i++) {
b[i] = BigInteger.ONE;
for (j = i - 1; j > 0; j--)
}
return b[m];
}

/* Calculate Catalan number directly iteratively (fastest) */
public static BigInteger catalan(int n) {
BigInteger[] c = new BigInteger[n + 1];
c = BigInteger.ONE;
for (int i = 1; i <= n; i++)
c[i] = c[i - 1].multiply(BigInteger.valueOf(4 * i - 2)).divide(
BigInteger.valueOf(i + 1));
return c[n];
}

/* Calculate Catalan number using factorial (slow) */
public static BigInteger catalan_fact(int n) {
return fact(2 * n).divide(fact(n + 1).multiply(fact(n)));
}

/* Calculate Catalan number using binomial coefficients (slowest) */
public static BigInteger catalan_binom(int n) {
return binomial(2 * n, n).divide(BigInteger.valueOf(n + 1));
}
}