# Problem 15: Lattice paths fast mathematical implementation

This post is not asking for a solution, rather I want to understand why my solution works. I accidentally found out that the problem given, computing the possible routes from top left to bottom right, comes down to computing (k2) choose k. For instance for a 2x2 grid, k would be 2, thus k2 = 4. So you would compute 4 choose 2, which equals 6.

I then looked up a fast implementation for n choose k. Which led me to this post:
Efficient computation of n choose k

I slightly tweaked the code.

``````
var size = 1000, logf = new Array(size);
logf = 0;
for (var i = 1; i <= size; ++i) logf[i] = logf[i - 1] + Math.log(i);
function latticePaths(k) {
let n = k * 2;
return Math.round(Math.exp(logf[n] - logf[n - k] - logf[k]));
}
latticePaths(4);
``````

But what I am interested in is, if anyone can explain to me why (k*2) choose k describes the problem mathematically

Challenge: Problem 15: Lattice paths

It’s because a square is a special case of a rectangular grid. In general, see here and here.

Roughly speaking, if you have a k x k square grid of points and you want to walk from one vertex to the non-adjacent one, you will need to make k steps vertically and k steps horizontally, or 2k steps. Out of those 2k steps, k of them will need to be vertical (or horizontal if you like), so to get a path, you need a combination of k vertical steps out of 2k total steps, or 2k choose k.

Note that the example for the problem shows a 2x2 grid of squares, but most of the analysis deals with points so a 2x2 grid of squares is a 3x3 grid of points.

Thanks a lot. The links you provided seem helpful. I’ll read into them more on occasion. Just a question, as you seem very comfortable with combinatorics, is there a way to express this problem with math as well?