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.

grid

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

Idea

A problem of 'combination'

From observation:

  • Each step can either go down or right, but cannot go down and right
  • Take totally 2 * grid_len steps to finish
  • Must take grid_len steps to go down, so is to go right
  • Among 2 * grid_len steps, if 'go down' steps is determined, other steps must be 'go right'

So this problem is simplified to caculate how many ways to choose grid_len steps (down / right) from 2 * grid_len steps.

Solution is $$ C_{steps}^{grid\_len} $$

In [1]:
from math import factorial
In [2]:
def solve(grid_len):
    steps = grid_len * 2
    return factorial(steps) // (factorial(grid_len) * factorial(steps - grid_len))
In [3]:
solve(2)
Out[3]:
6
In [4]:
solve(20)
Out[4]:
137846528820