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?
This is a problem I was working on a while ago from http://www.projecteuler.net
It occurred to me that I could count the number of routes using Catalan numbers, so I started to go that route but couldn't come up with the right answer. I got really complicated expressions, and ultimately ended up missing possible routes and/or overcounting.
How do I use Catalan Numbers to count the number of routes?
You don’t need Catalan numbers: you just need binomial coefficients. The number of such paths in an $m\times n$ grid is $\binom{m+n}m=\binom{m+n}n$.
The reason is quite simple: you must make a total of $m+n$ moves, consisting of $m$ moves down and $n$ to the right, in any order, and there are $\binom{m+n}m$ ways to choose which of the $m+n$ moves are down (or, equivalently, $\binom{m+n}n$ ways to choose which $n$ of them are to the right).