# Euler 15 – How many routes through a 20×20 grid?

Struggled to get my head around Euler problem 15:

Starting at the top left of a 20×20 grid and only moving right and down, how many routes are there?

I figured that this was a combinatorics problem but couldn’t see what to count or choose from.

Each time we select an element, there is one less to chose. Select all the elements, its the factorial. Each time an element of a set is chosen, there is one less to chose. Permutations let us select some of the elements in order.

$$_nP_k=\frac{n!}{(n-k)!}$$

Where n are options and k are the number chosen. What if order isn’t relevant? Then {a,b,c} and {b,a,c} are the same, so divide through by the number of duplicates:

$$_nC_k=\frac{n!}{k!(n-k)!}$$

I chanced on a blog post from João Ferreira, a Lecturer in Computer Science. His approach to this problem makes a couple of great observations I hadn’t seen. A degree only gives you the tools, the knack is knowing (a) what you are being asked to do and (b) which tools to use. I won’t steal his thunder so recommend reading his post. The number of choices is 2n and the choices are n.

$$_{2n}C_n=\frac{2n!}{n!(2n-n)!}=\frac{2n!}{n!n!}$$

This is trivial in R:

 123456 library(gmp) paths <- function(grid.size) { # Permutation (nCk) where {2n}C{n} return(           factorialZ(2 * grid.size) / (factorialZ(grid.size) * factorialZ(grid.size))) } print(paths(20))