## 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[0] = BigInteger.ONE;

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

b[i] = BigInteger.ONE;

for (j = i - 1; j > 0; j--)

b[j] = b[j].add(b[j - 1]);

}

return b[m];

}

/* Calculate Catalan number directly iteratively (fastest) */

public static BigInteger catalan(int n) {

BigInteger[] c = new BigInteger[n + 1];

c[0] = 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));

}

}

// 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[0] = BigInteger.ONE;

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

b[i] = BigInteger.ONE;

for (j = i - 1; j > 0; j--)

b[j] = b[j].add(b[j - 1]);

}

return b[m];

}

/* Calculate Catalan number directly iteratively (fastest) */

public static BigInteger catalan(int n) {

BigInteger[] c = new BigInteger[n + 1];

c[0] = 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));

}

}