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));
}
}