Calculating Binomial Coefficients with Dynamic programming


Calculating binomial coefficients can be important for solving combinatorial problems. A formula for computing binomial coefficients is this:


\dbinom{n}{m} = \dfrac{n!}{(n-m)!m!}

Using an identity called Pascal's Formula a recursive formulation for it looks like this:


\dbinom{n}{m} =
\begin{cases}
1 & \text{if $m=0$}\\
1 & \text{if $n=m$}\\
\dbinom{n-1}{m} + \dbinom{n-1}{m-1} & \text{otherwise}
\end{cases}

This construction forms [[http://mathworld.wolfram.com/PascalsTriangle.html Pascal's Triangle]]. Each number in the triangle is the sum of the two numbers directly above it.


\begin{array}{lllllllll}
\hline
n & \binom{n}{0} & \binom{n}{1} & \binom{n}{2} & \binom{n}{3} & \binom{n}{4} & \binom{n}{5} & \binom{n}{6} & \binom{n}{7} \\
\hline
0 & 1 & & & & & & & \\
1 & 1 & 1 & & & & & & \\
2 & 1 &  2 & 1 & & & & & \\
3 & 1 & 3 & 3 & 1 & & & & \\
4 & 1 & 4 & 6 & 4 & 1& & & \\
5 & 1 & 5 & 10 & 10 & 5 & 1 & & \\
6 & 1 & 6 & 15 & 20 & 15 & 6 & 1 & \\ 
7 & 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 \\
\hline
\end{array}

Finding a binomial coefficient is as simple as a lookup in Pascal's Triangle.

An effective DP approach to calculate binomial coefficients is to build Pascal's Triangle as we go along. The following code computes and keeps track of one row at a time of Pascal's triangle.

import java.math.BigInteger;
class BinomialCoefficients {
    /* Compute binomial coefficient (n choose m) using DP  */
    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];
    }
}

There are many more applications for Pascal's Triangle beyond finding binomial coefficients. For example:
Computer Science @ George Mason University