Lattice Paths

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 Number
Large Sum
Longest Collatz Sequence

Error 403 The request cannot be completed because you have exceeded your quota. : quotaExceeded

Share:

Recent Posts

Mathematics in Cancer Treatment

How Mathematics is Transforming Cancer Treatment Mathematics plays an increasingly vital role in the fight against cancer mesothelioma. From optimizing drug delivery systems to personalizing

Read More »