Problem 15: Starting in the top left corner, how many routes (without backtracking) are there through a 20 by 20 grid to the bottom right corner?

OK.  I am incredibly pleased with myself for solving this one almost entirely through mathematical proof.  Indeed, I’ve solved it generally for NxN grids.  The only time I relied on any outside resources (http://answers.yahoo.com/question/index?qid=20100403083143AAACNJs) was to find a formula for calculating the number of multiset permutations (knowing at that point that it was exactly what I needed).  So, here goes…

Two things are clear from the statement of our problem.  First, every route has length N+N=m.  Second, it takes equally as many downward as rightward movements along the route to make it to the bottom right corner. Hence, we must find the number of permutations of elements in the multiset of length m containing m/2 downward movements and m/2 rightward movements.

let problem15a =
    let fact m = {1I..m} |> Seq.fold (*) (1I)
    let multiset m = (fact m) / ((fact (m/2I))*(fact (m/2I)))
    multiset 40I