Problem 15: Lattice paths fast mathematical implementation

[MartinElsaesser]

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] = 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

Link to the challenge:

freeCodeCamp.org

[jeremy.a.gray]

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.

[MartinElsaesser]

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?

No repeats please

I’ve had some success deriving formulas for specific character constellations, e.g. two double characters and an arbitrary amount of characters with every character being unique. I did this for two sets of two double characters and an arbitray number of following unique characters and a few more cases too, but it got increasingly harder and as I am new to combinatorics I am struggling here.

[JeremyLT]

I think there is theoretically a combinatorial solution to that one, but it’s unconstrained enough that it would be a beast.