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