This one isn’t even funny…

Starting in the top left corner of a 2×22 \times 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

The six routes through a 2 by 2 grid, using only right and down moves

How many routes are there through a 20×2020 \times 20 grid?

Your first thought would be to generate the routes, but for a 20×2020 \times 20 grid, those amount to BILLIONS and you’d try to do it recursively too! Forget it.

But if you have some CompSci-level math background, though, you’ll remember this one—reading The Art of Computer Programming, Vol. 4 also helps. It’s a matter of combinatorics and if we take ww for the width and hh for the height, all we need to calculate is:

(w+h)!w! h!. \frac{(w+h)!}{w!\,h!}.

Every path consists of exactly 20 moves right and 20 moves down. Choosing which 20 of the 40 positions are right moves uniquely determines a path, so the answer is the binomial coefficient (4020)\binom{40}{20}.

from math import comb

width = height = 20
print(comb(width + height, width))

math.comb computes the integer result directly, without constructing three factorials. The answer is 137846528820.