## Question

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?

## Commentary

The grid can be expressed as Pascal’s Triangle:

```
1
1 1
1 (2) 1
1 3 3 1
1 4 (6) 4 1
1 5 10 10 5 1
1 6 15 (20) 15 6 1
```

Note that the solution for a 1x1 grid is 2, a 2x2 grid is 6, and a 3x3 grid is 20.

If we compare these solutions to Pascal’s Triangle, we see that they correspond to the 1st element in the 2nd row, the 2nd element in the 4th row, and the 3rd element in the 6th row, respectively. (Note that Pascal’s Triangle is zero-indexed.)

The binomial coefficient $\binom {n} {k}$ can be used to determine the $k$th element in the $n$th row of Pascal’s Triangle. Thus, we could express the aforementioned solutions as $\binom {2} {1}$, $\binom {4} {2}$, and $\binom {6} {3}$, respectively.

Thus, a general solution for grids of size $x$ is

$\displaystyle routes = \binom {2x} {x}$.

## Haskell

```
factorial :: Integer -> Integer
factorial n = product [1..n]
choose :: Integer -> Integer -> Integer
choose n k = div (factorial n) $ factorial k * factorial (n - k)
main :: IO ()
main = print $ choose 40 20
```

```
$ ghc -O2 -o binom binom.hs
$ time ./binom
real 0m0.002s
user 0m0.000s
sys 0m0.000s
```

## Python

```
#!/usr/bin/env python
from gmpy2 import comb
print(comb(2 * 20,20))
```

```
$ time python3 grid-routes.py
real 0m0.027s
user 0m0.020s
sys 0m0.004s
```

## Ruby

```
#!/usr/bin/env ruby
class Integer
def choose(k)
(self-k+1 .. self).inject(1, &:*) / (2 .. k).inject(1, &:*)
end
end
puts 40.choose(20)
```

```
$ time ruby pascal.rb
real 0m0.039s
user 0m0.028s
sys 0m0.008s
```

## Rust

```
fn choose(n: u64, k: u64) -> u64 {
(0..k).fold(1, |acc, i| acc * (n - i) / (i + 1))
}
fn main() {
println!("{}", choose(40, 20));
}
```

```
$ rustc -C target-cpu=native -C opt-level=3 -o binom binom.rs
$ time ./binom
real 0m0.001s
user 0m0.000s
sys 0m0.000s
```