# Project Euler: Problem 15 – Lattice paths

#### 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.

```String answer = "";

BigInteger value = nChooseM(40,20);

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.

1. George Tang

may I see your “nChooseM” function?

2. ```//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));`