En una $h \times h$ plaza de la celosía, el recuento de todos los caminos de $(0,a)$ a $(h-1,b)$, $a,b \in [0,h-1]$, con movimientos en diagonal permitido

Question

Considere la posibilidad de una $h \times h$ vertical plaza de celosía, donde un punto se define por $(x,y)$, $x,y \in [0,h-1]$. Una ruta de acceso válida comienza a partir de los bordes de la izquierda, $(0,a)$, $ a \in [0,h-1]$ y termina en el límite derecho $(h-1,b)$, $ b \in [0,h-1]$. Movimientos permitidos son:

• Diagonal, como $(0,0) \rightarrow (1,1)$, o
• A la derecha, como $(0,0) \rightarrow (1,0)$.

Movimiento Vertical o de cualquier movimiento a la izquierda no es válido.

¿Cuál es el número total de todas estas vías? Su posible calcular las rutas de acceso mediante programación a un cierto $h$ (después de la $h=8$ se vuelve muy lento). Estoy buscando una forma cerrada de la expresión. Aquí está el número de caminos para $h=2,\ldots,7$

Tabla 1:

• h=2, 4 caminos
• h=3, 17 rutas
• h=4, 68 rutas
• h=5, 259 caminos
• h=6, 950 caminos
• h=7, 3387 caminos

Un problema más general:

Consideremos ahora nos podemos mover en toda la diagonal de los ejes. Por ejemplo, considere un $4\times 4$ celosía. De $(0,0)$ podemos ir a $(1,0)$, $(1,1)$, $(1,2)$ o $(1,3)$. Permite indicar estos movimientos en diagonal con $a$-diagonal. Por lo tanto, $(0,0) \rightarrow (1,0)$ $0$- movimiento diagonal, $(0,0) \rightarrow (1,1)$ $1$- movimiento diagonal, $(0,0) \rightarrow (1,2)$ $2$- movimiento diagonal, $(0,0) \rightarrow (1,3)$ $3$- movimiento diagonal, etc.

Denota el conjunto de todas las rutas que parten de los bordes de la izquierda $(0,a)$ y final a la frontera derecha $(h-1,b)$, $ b \in [0,h-1]$, y tener al menos un $a$-movimiento diagonal, pero no un $(a+1)$-movimiento diagonal con $\mathcal{B}_a$. El enunciado del problema es: Calcular el número de rutas en cada una de las $\mathcal{B}_0, \mathcal{B}_1,\ldots,\mathcal{B}_{h-1}$. (Tenga en cuenta que los números en la Tabla 1 se dan a $\mathcal{B}_0 + \mathcal{B}_1$). La siguiente tabla muestra los valores de $h=2$$h=7$:

Cualquier sugerencia sobre cómo abordar esto sería muy apreciado.

Edit: El movitation para este problema es calcular el número de funciones lineales a trozos $f:[0,1]\rightarrow [0,1]$ que tienen un máximo de derivados de 0 (dado por $\mathcal{B}_0$), 1 (dada por $\mathcal{B}_1$), $\ldots$, $h-1$ (dado por $\mathcal{B}_{h-1}$).

Answer 1

La única dificultad real aquí es lograr una buena fórmula.

Escribir una fila de $h$: $$1\quad1\quad1\quad\ldots\quad1\quad1\quad1$$ A continuación, escribe, debajo de cada número, la suma de los dos/tres números directamente encima o un lugar al lado: $$2\quad3\quad3\quad\ldots\quad3\quad3\quad2$$ Y repetir esta $h-1$ veces. El final de la fila se suma a la cantidad deseada. Así que usted puede encontrar incluso con la mano que para $h=8$, la respuesta es $11814$. Su problema más general puede ser resuelto de una forma similar, sumando los tres/cuatro/cinco más cercano números en su lugar.

La OEIS enlace en los comentarios tiene un par de fórmulas. La primera es en términos de Motzkin números, que son de por sí bastante difícil dar una cerrada fórmula para. El más simple de recurrencia es uno de Václav Kotěšovec: $$a_n = \frac{(10n^2-39n+23)a_{n-1}-3(2n^2-n-9)a_{n-2}-9(n-3)(2n-5)a_{n-3}}{(n-1)(2n-7)}$$