# 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}$ ?

-
Is there any particular reason that it is a square? if I get the problem correctly the mouse will never get higher than $\frac n2$ for any suitable path. –  Simon Markett May 27 '12 at 16:52
What do you mean by "leap"? By diagonal leap, do you mean just single steps, or any move to any other point on the same diagonal? Does the mouse move like a chess king, or a chess queen? –  Thomas Andrews May 27 '12 at 17:23
Thomas: more like a king –  Henry May 27 '12 at 17:27

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.

-
From the Wiki article, that seems like it might be a little off - the "path" version is the number of paths of length $n$ from $(0,0)$ to $(0,n)$. But the OP's question is asking for paths of length $n$ from $(0,0)$. to $(0,n-1)$, or else you'd be dealing with an $n+1\times n+1$ grid. In particular, the Motzkin example never requires all steps to be at least to the right. –  Thomas Andrews May 27 '12 at 17:18
@Thomas: I think you have misunderstood the OP's question. Also, it seems that you didn't read the Wikipedia article I linked to (or even look at the pictures). –  TonyK May 27 '12 at 17:21

You will find a mass of formulae at OEIS A001006

If I were working this out from scratch I would use

$$\sum_{k=0}^{\lfloor n/2 \rfloor} {n \choose 2k} \frac{1}{k+1} {2k \choose k} =\sum_{k=0}^{\lfloor n/2 \rfloor} \frac{n!}{k! (k+1)!(n-2k)!}$$

as a combination of $k$ diagonal up steps, $k$ diagonal down [but not going below the starting point so involving Catalan numbers] and $2n-k$ horizontal.

So for $n=5$ this gives $\dfrac{5!}{0!1!5!} + \dfrac{5!}{1!2!3!} + \dfrac{5!}{2!3!1!} = 1 + 10 + 10 =21.$

-