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 numbers are given by the following closed-form equations:


C_n = \dfrac{1}{n+1}{\dbinom{2n}{n}} = \dfrac{(2n)!}{(n+1)!\,n!} \qquad\mbox{ for }n\ge 0.

However, the equations above require computation of binomial coefficients or factorials. An alternative way to compute Catalan numbers is through its recurrence relations:


C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\displaystyle\sum_{i=0}^{n}C_i\,C_{n-i}\quad\mbox{for }n\ge 0.

Which can be done with Dynamic Programming. However, Catalan Numbers also go by this recurrence relation that is even easier to compute iteratively:


C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\dfrac{2(2n+1)}{n+2}C_n

// 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));
    }
}
Computer Science @ George Mason University