### Lattice Paths Problem

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

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

Solution:

```void Solution()
{
//Lattice Path Problem
//The number of possible path at (i,j) = BinCoff(i+j,j)
// So for 20x20 matrix it will be
long x = BinomialCoefficient(40, 20);
}

static long BinomialCoefficient(long n, long k)
{
// return fact(n) / (fact(k) * fact(n - k));

long divFactor = k > (n - k) ? k : (n - k);
long restProd = 1;
bool flag = true;
long counter = 1;
if (divFactor == k)
{
for (long i = 0; i < (n - k); i++)
{
restProd = restProd * (k + 1 + i);
if (restProd % counter == 0 && flag)
{
restProd = restProd / counter;
//flag = false;
counter++;
}
}
return restProd;// / fact(n - k - counter);
}
else
{
for (long i = 0; i < k; i++)
{
restProd = restProd * ((n - k) + 1 + i);
}
return restProd / fact(k);
}

}

static long fact(long i)
{
if (i == 0)
return 1;
else
return i * fact(i - 1);
}
```