4
$\begingroup$

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

  • 0
    Thomas: more like a king2012-05-27

2 Answers 2

4

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.

  • 1
    @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).2012-05-27
2

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.$