Project Euler Problem 15
Starting in the top left corner of a 2 times 2 grid, and only being able to move to the right and down, there are exactl
Solution
Answer: 137846528820
To go from the top-left corner to the bottom-right corner of a $20\times20$ grid, every valid path consists of:
- $20$ moves right
- $20$ moves down
So each route is just an arrangement of $40$ moves where we choose which $20$ are right (or down).
Thus the number of routes is the binomial coefficient:
$$\binom{40}{20}$$
Using the combinatorial formula:
$$\binom{40}{20}=\frac{40!}{20!,20!}$$
A compact Python solution is:
import math
answer = math.comb(40, 20)
print(answer)
Evaluating this gives:
$$137846528820$$
This matches the known lattice-path counting formula, so the computation is correct.
Answer: 137846528820