Problem 15: Lattice paths
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?
Algorthim:
This is a very common brain teaser question. The difference between two different paths is the difference in which direction the path takes at any given lattice site: we can either take right or down. Hence, the problem boils down to number of ways we can arrange 10 Down's aand 10 Right's in 20 positions (listed 1-20)
For example, in a 4x4 lattice site, we can go Down, Down, Right Right. Notice that we need 2 Down's and 2 Right's always. $$ \underline{D}\, \underline{D} \, \underline{R} \, \underline{R} $$
Or, we can go Down Right Down Right $$ \underline{D}\, \underline{R} \, \underline{D} \, \underline{R} $$
These two are two differennt paths
So, how many ways are there? 20 choose 10 or: $$ {20\choose10} = 137846528820 $$ The code below calculates for any rectangular shape
Code:
Result:
Answer: 137846528820
Runtime: N/A