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.

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:

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

(m + n)! / n! (m + n - n)! = (m + n)! / m! (m + n - m)!
(m + n)! / n!m! = (m + n)! / m!n!

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