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?

Solution

p15.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/usr/bin/python
# -*- coding: utf-8 -*-
if __name__ == '__main__':
(steps, a, b) = (20, 1, 1)
i = steps * 2
while i > steps:
a *= i
i -= 1
while steps > 1:
b *= steps
steps -= 1
print a / b

I’m the 86747th person to have solved this problem.