Project Euler - Problem 15

Today I came across Problem 15 from Project Euler,

Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner.
Routes for 2x2 grid
How many routes are there through a 20x20 grid?

Lets write the routes for 2x2 grid as list of right (R) and down (D) segments. The possible routes are: RRDD, RDRD, RDDR, DRRD, DRDR, DDRR. You may notice that all these routes consist of 2 right segments and 2 down segments for a total of 4 segments.

It took me awhile to figure out that this is a combinations problem. Until I realized that once you have chosen the positions of the Rs, then Ds must occupy all the other positions. That is the number of arrangements is just the number of different ways of selecting the positions of the Rs from the available positions in the route.

The number of k-combinations (each of size k) from a set S with n elements (size n) is:
n! / k! (n - k)!

So for a NxN grid there are 2N available positions and we need to choose N positions. Plugging into the forumla we get

(2n)! / n! (2n - n)!
= (2n)! / n!n!
= (2n)! / n!2
For a MxN grid there are (M+N) available positions and we need to choose N or M positions. Note choosing either M or N results in the same result:
(m + n)! / n! (m + n - n)! = (m + n)! / m! (m + n - m)!
(m + n)! / n!m! = (m + n)! / m!n!
And here is the Haskell code:
factorial :: Integer -> Integer
factorial n = product [1..n]
 
grid_routes :: Integer -> Integer -> Integer
grid_routes n m = (factorial (m+n)) `div` ((factorial m) * (factorial n))
 
main = print $ grid_routes 20 20

Trackback URL for this post:

http://grom.zeminvaders.net/trackback/11

Small note to your derivation

Your derivation:
(m + n)! / n! (m + n - n)! = (m + n)! / m! (m + n - m)!
(m + n)! / n!m! = (m + n)! / m!n!

seems unnecessary to me. Why did you do the second step? I'd simply resolve (m + n - n)!=(m)!=m! and therefore:
(m + n)! / n! (m + n - n)! = (m + n)! / n!m! = (m + n)! / m!n!

Or did I oversee something?

Btw, your post helped me a lot to solve the problem. I'm actually using project euler as a motivation for me to get deeper into mathmatics and I'm always happy to find completely new branches/aspects like combinatoric/combinations :)

@Stefan Lotties

> Why did you do the second step?

The left side is when k = m. The right side is when k = n. I am just showing that it comes down to the same result.

Hey, I'm loving your

Hey, I'm loving your ZemScript. It's just what I needed - a language with minimal baggage. I'm planning on using it as a scripting language for this AI based game I'm making. Due to the nature of the game, I really wanted to restrict the player from having a random number function, and as far as I know your language didn't have one.