Project Euler – Lattice Path (Part 6)

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.

RDRD

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 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:

nCr

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

binomial_coefficient_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:

binomial_coefficient_multiplicative_formula_2

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

combinatorial_algorithm

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s