From charlesreid1

Problem Statement

Problem 53 asks about values of the binomial coefficient, a.k.a. n-choose-k. For some values of n and k, the resulting n-choose-k value can exceed 1 million. This question asks how many binomial coefficients n-choose-k exceed 1 million, for n = 1 to 100.

Solution Explanation

The solution here creates a matrix of values. We know that if n = k, the binomial coefficient is 1, so we can think of a square matrix, one dimension being n and the other being k, where the values along the diagonal are 1. We now have a discrete set of values on a grid, 100 x 100, and we wish to count how many squares where the n-choose-k value will exceed 1 million.

My clever solution, which enabled me to save a loooot of time that would otherwise be wasted finding factorials, was to use the fact that if n-choose-k is bigger than 1 million, then LOG(n-choose-k) should be bigger than LOG(1 million).

Taking the log of the binomial expression gives:

\log \left( \dfrac{n!}{k! (n-k)!} \right) 
= \log \left[ \dfrac{n \times (n-1) \times \dots \times 1 }{ ( k \times (k-1) \times \dots \times 1 )( (n-k) \times (n-k-1) \times \dots \times 1 )} \right]

Now applying log properties simplifies this to:

\log \left( \dfrac{n!}{k! (n-k)!} \right) 
= \log \left[ n \times (n-1) \times \dots \times 1 \right] - \log \left[ k \times (k-1) \times \dots \times 1 \right] - \log \left[ (n-k) \times (n-k-1) \times \dots \times 1 \right]

Further simplifying turns this into a trivial sum:

\log \left( \dfrac{n!}{k! (n-k)!} \right) 
= \sum_{p=1}^{n} \log p - \sum_{q=1}^{n-k} \log q - \sum_{r=1}^{k} \log r

thus reducing the problem of marking a "square" on our 100 x 100 n vs. k grid reduces to adding numbers that are O(10), instead of multiplying numbers that are O(100000000...)

The final comparison being done is:

\sum_{p=1}^{n} \log p - \sum_{q=1}^{n-k} \log q - \sum_{r=1}^{k} \log r < \log(10000)

If this is true, n-choose-k is less than 1 million; if it is false, n-choose-k is greater than 1 million.

Solution Code


public class CombinatoricSelections {
	public static void main(String[] args) { 

	/** Nice easy test. This should be bigger than 1 million - should return true. */
	public static void test() { 
		System.out.println("isBigger(23,10) = "+isBigger(23,10));

	/** Solve the problem. */
	public static void doit() {
		int MAX = 100;
		int count = 0;
		boolean[][] isBig = new boolean[MAX][MAX];
		for(int nm1=0; nm1<MAX; nm1++) { 
			for(int rm1=0; rm1<MAX; rm1++) { 
				// determine if n C r > 1M
				int n = nm1+1;
				int r = rm1+1;
				boolean big = isBigger(n,r);
				isBig[nm1][rm1] = big;
				if(big) count++;
		System.out.println("Total number of n Choose r values that are greater than 1M: "+count);

	/** Boolean: is n choose r bigger than 1 million? */
	public static boolean isBigger(int n, int r) {
		int d = (n-r);
		double LHS = 0.0;
		for(int j=0; j<d; j++) {
			LHS += Math.log(r+d-j) - Math.log(d-j);
		double RHS = Math.log(1000000);
		return LHS > RHS;