**Problem 15:**

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20×20 grid?

**Idea:**

I recognized this as a Binomial Coefficient problem of given `n` things, how many ways could you choose `m` things? I looked briefly but didn’t find any Java classes that implemented this, so I implemented it myself.

Note: “nChooseM” is a Mathematical Combination function I implemented using BigInteger. 40 choose 20 because there are 40 moves (20 left, 20 down), in the 20×20 grid. In the example, it would be 4 choose 2 = 6.

may I see your “nChooseM” function?

I implemented the factorial method from the Binomial Coefficient link above: n! / (m! (n-m)!)

Basically it’s: (n & m are int parameters, nFact, mFact, and nMinusM are BigIntegers)

`//n!`

for(int i = n-1; i > 1; i--) {

nFact = nFact.multiply(BigInteger.valueOf(i));

}

//m!

for(int i = m-1; i > 1; i--) {

mFact = mFact.multiply(BigInteger.valueOf(i));

}

//(n-m)!

for(int i = (n-m)-1; i > 1; i--) {

nMinusM = nMinusM.multiply(BigInteger.valueOf(i));

}

`return nFact.divide(mFact.multiply(nMinusM));`

Pingback: Project Euler: Problem 53 – Combinatoric selections - Pursuit of Intellectual Curiosity