Given an n x n grid, how many ways from one corner to the other if legal moves are one square or two squares down or to the right

combinatorics

Given an $n\times n$ grid, how many different ways to move from the upper left corner to the the lower right corner if a move consists of either one square down or to the right, or two squares either down or to the right. For clarity, any of the following could be considered one move: D, R, DD, RR, DR, RD

If allowed to move just one square, it's simply ${2n-2 \choose n-1}$, i.e. $2n-2$ total D and R moves are required, and $n-1$ must be say D.

But getting hung up on the two squares in either direction being a legal move.

I've given it a go with counting strings of the legal moves, but hasn't amounted to much.

Best Answer

You can look it as a string of $D$s and $R$s just like the single move case. Having made the string, now you can break it up into $1$s and $2$s. It becomes the number of ways to fill a $1 \times 2n-2$ rectangle with $1 \times 1$ blocks and $1 \times 2$ blocks. You may have seen that problem-we have several times.