This will be my last blog post on the lattice path problem for now. As always, full credit goes to Pim Spelier.

After all that theory I want to do some reading on real life applications of lattice paths.

Also I have some other blog topics and Project Euler problems on my mind.

**The final solution to the lattice path problem is shockingly simply, if you know your math.** I fiddled with a similar idea when I started working on this, but failed to figure it out in the end. Because I don’t know my math (yet).

Enter combinatorics….

Let’s have a look at the 2 x 2 grid. Whatever path you take from the top left to the bottom right corner, you always have to go the same number of steps right- and downwards.

So it is either *RRDD*,* RDRD*,* RDDR*,* DRRD*,* DRDR *or* DDRR *for the 2 x 2 grid.

Always a combination of two steps to the right and two steps to the bottom. The number of steps total is defined by the grid size. 2 x 2 = 4 in this example.

For a grid of width *n* and height *m* it’s *n*-times *R* and *m*-times *D* with a total step length of *n* x *m*.

Now all you have to figure out is, how many unique combinations of *Rs* and *Ds* in a string of length *n* x *m *exist.

Actually you only have to know the unique ways of placing *Rs* in a string of length *n *x* m*. Once the *Rs* are in place, the* Ds* are automatically in place as well.

The math you need to figure this one out is called binomial coefficient, short *nCr* for *from n choose r.*

How many unique ways can two *Rs* placed in a string of length 4?

It is from 4 choose 2, which is 6:

Several ways to compute the binomial coefficient exist, one of them being a multiplicative formula:

Our grid is a perfect square (2 x 2, 3 x 3, 4 x 4…20 x 20). As shown above for a 2 x 2 grid it’s from 4 choose 2. For a 3 x 3 grid it’s from 6 choose 3 and so on. Therefore the relation between *n* and *k* is *2n* to *n*:

And a sum can be implemented using a for-loop:

Done! Now I need to install me some Latex. Powerpoint is such a pain.