A mouse leaping along the square tile A $n \times n$ square is made of square tiles of dimensions $1\times1$. A mouse can leap along the diagonal or along the side of square tiles. In how many ways can the mouse reach the right lower corner vertex of the square from the lower left corner vertex of the square leaping exactly $n$ times? In one of my exam, I encountered a particular version of this problem with $n=5$. With a semi-brute force (case counting) kind of approach I derived the answer as $21$. How to derive the general solution for any $n \in \mathbb{N}$ ?

The general solution is the $n$th Motzkin number $-$ the number of ways of drawing non-intersecting chords between $n$ points on a circle. There is a Wikipedia article on Motzkin numbers, and an entry (A001006) in the OEIS database. The OEIS entry gives several recurrence relations and generating functions, but they are all very messy.