[Golang] Lattice paths - Problem 15 - Project Euler

Problem: [1]

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

Solution:

Observe the case of a 2x2 grid. We can found that to move from top left to bottom right, we need to move 2 down steps and 2 right steps. The total number of routes in 2x2 grid is hence equivalent to total number of combinations of 2 down steps and 2 right steps in a row, i.e., (42) = (4!)/(2!2!) = 6.

So, the routes in 20x20 grid = (2010) = (20!)/(10!10!) = 184756

---

References:

[1]	Lattice paths - Problem 15 - Project Euler