Problem

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?

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

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

Answer

137846528820

---

Python

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

---

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)

---

Clojure

#!/usr/bin/env clojure
; compute pascal's triangle
(defn ** [x n]
  (. (. java.math.BigInteger (valueOf x)) (pow n)))

(defn pascal [n k]
  (cond 
    (= k n) 1
    (or (< n 0) (< k 0)) 0
    :else 
    (+
      (pascal (- n 1) (- k 1))
      (pascal (- n 1) k))))

(defn pascal-row [n]
  (map #(pascal n %) (range (+ n 1))))

(defn pascal-triangle [num-rows]
  (map #(pascal-row %) (range num-rows)))

(dorun (map println (pascal-triangle 10)))
(println (pascal 5 3))

---

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

---

Java
``java
import java.math.BigInteger;

public final class p016 implements EulerSolution {

public static void main(String[] args) {
    System.out.println(new p016().run());
}


/* 
 * We implement this solution in a straightforward way with help from BigInteger.
 */
public String run() {
    String temp = BigInteger.ONE.shiftLeft(1000).toString();
    int sum = 0;
    for (int i = 0; i < temp.length(); i++)
        sum += temp.charAt(i) - '0';
    return Integer.toString(sum);
}

}

________
Mathematica
```mathematica
(* 
 * We implement this solution in a straightforward way thanks to
 * Mathematica's built-in functions and arbitrary precision integer type.
 *)
Total[IntegerDigits[2^1000]]