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

Since we can not backtrack, we can only move down and right. If we have a 2x2 grid, this means every route consists of exactly 2 right moves and 2 down moves. We can think of the routes as a set of moves, such as (d d r r), and the total number of routes will be all the different combinations of the set minus the identical combinations. To find the number of unique combinations, suppose we have the route (d d r r). Treating each move distinctly, lets write the set as (d1 d2 r1 r2). Notice how this route is equal to the route(d2 d1 r2 r1), and we only want to count this as one route. It turns out that the number of unique routes per combination is 2!*2! = 4: (d1 d2 r1 r2) (d1 d2 r2 r1) (d2 d1 r1 r2)(d2 d1 r2 r1). This means each route in the set of all possible route combinations, 4!, will have 3 other identical routes in the set, resulting in 4!/(2!2!) unique routes. This formula applies to larger grids as well.

(defun factorial (n &optional (acc 1))
  (if (<= n 1)
      acc
      (factorial (- n 1) (* acc n))))

(defun grid-routes (x-dim y-dim)
  "Calculates the number of routes from the top left corner
of a grid to the bottom right corner, without backtracking"
  (let ((total-number-of-moves (+ x-dim y-dim)))
    (/ (factorial total-number-of-moves)
       (* (factorial x-dim)
           (factorial y-dim)))))

(defun euler-15 ()
  (grid-routes 20 20))