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 exactly $6$ routes to the bottom right corner.
How many such routes are there through a $20 \times 20$ grid?
The number of routes through a square grid is actually a problem of combinatorics, specifically, it can be solved using binomial coefficients, or “combinations,” from probability theory.
This problem boils down to how many ways we can arrange 20 rights (R) and 20 downs (D) in a sequence. This is because from the top left corner to the bottom right of a 20×20 grid, we must move right 20 times and down 20 times — no more, and no less. Therefore, we want all unique sequences of 20 Rs and 20 Ds.
The binomial coefficient, C(n+k-1,k), will provide the solution, where n is the number of rows and k is the number of columns. In the case of a 20×20 grid, n=k=20, so the binomial coefficient simplifies to C(20+20,20), or “40 choose 20.”
This binomial coefficient is calculated as `(40!) / (20! * 20!)`, where “!” denotes factorial, meaning the product of all positive integers up to that number.
So, the solution is:
(40*39*38*…*21) / (20*19*18*…*1)
This equals 137846528820 routes.
More Answers:
Highly Divisible Triangular NumberLarge Sum
Longest Collatz Sequence