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?
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
|||Lattice paths - Problem 15 - Project Euler|