## Calculating Binomial Coefficients with Dynamic programming

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

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

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.

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];

}

}

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:

- Many other numerical patterns can be extracted from diagonals on Pascal's Triangle:
- Fibonacci numbers
- Triangular numbers
- Tetrahedral numbers
- Pentatope numbers
- D-Simplex numbers

- Coloring the odd numbers gives you a fractal-like pattern - the Sierpinski triangle.
- If all numbers in Pascal's Triangle are connected in a grid fashion as nodes in a graph, the Pascal number in some node A provides the number of paths along edges from the top node to A.
- On any row m, where m is odd, the middle term minus the term two spots to the left equals a Catalan number, specifically the (m + 1)/2 Catalan number.