Un ratón, saltando junto a la plaza de baldosas

Question

Un $n \times n$ plaza es de baldosas cuadradas de dimensiones $1\times1$. Un ratón puede saltar a lo largo de la diagonal o lateral de la plaza de las baldosas. De cuántas maneras puede el ratón llegar a la esquina inferior derecha del vértice del cuadrado de la esquina inferior izquierda del vértice de la plaza del salto exactamente $n$ veces?

En uno de mis exámenes, me he encontrado con una versión particular de este problema con $n=5$. Con un semi-fuerza bruta (el caso de contar) tipo de enfoque que derivado de la respuesta $21$. La forma de obtener la solución general para cualquier $n \in \mathbb{N}$ ?

Answer 1

La solución general es de la $n$th Motzkin número $-$ el número de maneras de dibujo no de intersección de los acordes entre $n$ puntos en un círculo. Hay un artículo de la Wikipedia en Motzkin números, y una entrada (A001006) en la OEIS de la base de datos. La OEIS entrada da varias relaciones de recurrencia y la generación de funciones, pero todos ellos son muy desordenado.

Answer 2

Usted encontrará una masa de fórmulas en OEIS A001006

Si yo estuviera trabajando en esto desde cero, me gustaría utilizar

$$\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)!}$$

como una combinación de $k$ diagonal pasos, $k$ diagonal hacia abajo [pero no va por debajo del punto de partida, así que involucran números de catalán] y $2n-k$ horizontal.

Así, por $n=5$ esto da $\dfrac{5!}{0!1!5!} + \dfrac{5!}{1!2!3!} + \dfrac{5!}{2!3!1!} = 1 + 10 + 10 =21.$