Binomial Coefficient

Problem:

The number of ways to choose m items from n items can be presented as (n, m),
which is n! / ((n-m)! * m!), if you calculate directly by factoring it, it either will take you tons of time to compute it, or it may cause arithmetic overflow.

Solution:

So there is an easy and more secure way to calculate it.

(n, m) = (n-1, m-1) + (n-1, m).

This can be explains as :

Consider whether the n th element appears in one of the (n, m) subsets of m elements. If so, we can complete the subset by picking m−1 other items from the other n −  1. If not, we must pick all m items from the remaining n −  1.

Source Code:

/**
 * Copyright (C) 2012 Antonio081014
 */

/**
 * This is a demonstration of how to calculate binomial coefficient with dynamic
 * programming.
 * 
 * @author antonio081014
 * @time: Dec 5, 2012, 3:17:27 PM
 */
public class BinomialCoefficient {

    public static void main(String[] args) {
 BinomialCoefficient main = new BinomialCoefficient();
 main.run();
    }

    public void run() {
 System.out.println(binomial_coefficient(10, 2));
    }

    /**
     * Compute binomial_coefficient, choose m from n.
     * 
     * @param n
     *            The total number of items could be selected.
     * @param The
     *            number of item to select.
     * @return binomial coefficient.
     */
    public long binomial_coefficient(int n, int m) {
 long[][] table = new long[n + 1][n + 1];
 // Initialize the base case;
 for (int i = 0; i <= n; i++) {
     table[i][0] = 1;
     table[i][i] = 1;
 }

 for (int i = 1; i <= n; i++)
     for (int j = 1; j < i; j++) {
  table[i][j] = table[i - 1][j] + table[i - 1][j - 1];
     }
 return table[n][m];
    }

}