Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Starting in the top left corner of a 2 x 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20 x 20 grid?

**********

After doing a bit of research on this problem, it seems as though a simple *Combinations* formula will provide the answer. We know that any path will have 40 moves (20 right + 20 down), so for C(n,r) – n will equal 40 and r (the number of right moves) will equal 20 – C(40,20). Then we just plug the numbers into the formula – the ! means ‘factorial’. In order to solve this problem, I asked a question about creating a big.Int factorial in go on Stackoverflow.

n!

C(n,r) = ———-

r!*(n-r)!

The number of how many good routes we have can be found by finding how

many combinations of 20 R’s we can have in our 40 moves, so we want to

calculate:

40!

C(40,20) = ———-

20!*(40-20)!

Helpful Links:

- Possible Paths across a Rectangular Grid – http://mathforum.org/library/drmath/view/66728.html
- Go big.Int factorial with recursion – http://stackoverflow.com/questions/11270547/go-big-int-factorial-with-recursion

### One Possible Solution: Go – uses recursion for the *factorial* function

package main import "fmt" import "math/big" func main() { n := big.NewInt(40) // The total number of moves for any one path (right + down) r := big.NewInt(20) // The total number of right moves for any one path t := big.NewInt(0).Sub(n, r) // Part of Denominator x := big.NewInt(0).Mul(factorial(r), factorial(t)) // The complete Denominator Answer := big.NewInt(0).Div(factorial(n), x) // Divide the Numerator by the Denominator fmt.Println(Answer) } func factorial(n *big.Int) (result *big.Int) { // This function finds the factorial of a number. For example: 5! = 5 * 4 * 3 * 2 * 1 = 120 b := big.NewInt(0) c := big.NewInt(1) if n.Cmp(b) == -1 { result = big.NewInt(1) } if n.Cmp(b) == 0 { result = big.NewInt(1) } else { result = new(big.Int) result.Set(n) result.Mul(result, factorial(n.Sub(n, c))) } return }