Trayectorias reticulares con movimientos $(1, 0)$ , $(1, 1)$ y $(1, -1)$

Question

Encuentre una fórmula cerrada para la función generadora que cuenta el número de caminos de la red desde $(0, 0)$ a $(n, 0)$ que nunca bajan de $y=0$ y consisten en los movimientos $(1, 0)$ , $(1, 1)$ y $(1, -1)$ .

---

Me he atascado intentando resolver este problema y no avanzo.

Preferiría pistas y esquemas sobre cómo resolver este problema, más que una solución completa.

Mi idea hasta ahora es sumar sobre el posible número de $(1,0)$ se mueve. La eliminación de estos $i (1,0)$ movimientos crearía una situación similar a las trayectorias de Dyck de longitud $n-i$ contados por el $(n-i)/2$ El número catalán. El $i (1,0)$ movimientos pueden ser reinsertados en $\binom ni$ formas. Sin embargo, esto da lugar a una fórmula en la que el índice $i$ debe tener la misma paridad que $n$ y no sé cómo continuar esta idea a una función generadora en forma cerrada.

Answer 1

Recordemos cómo se deriva la función generadora de las trayectorias catalanas. Se observa la primera vez que la trayectoria vuelve a cero. Esto factoriza de forma única $C_{n}$ como $(\nearrow, C_k,\searrow, C_{n-1-k})$ para algunos $k$ entre $0$ y $n-1$ para que $$ C_n=\sum_k C_kC_{n-1-k}\text{ for }n\ge 1,C_0=1\implies C(x)=1+xC(x)^2 $$ Ahora intentemos hacer lo mismo con sus caminos. Dejemos que $M_n$ denotan el conjunto de caminos hacia $(n,0)$ . Nosotros casi todavía tienen la factorización $$ M_n\stackrel{?}=\bigcup_{k=0}^{n-2}(\nearrow, M_k,\searrow, M_{n-2-k}) $$ mirando la primera vez que la trayectoria vuelve a cero. Sin embargo, esto sólo tiene en cuenta las trayectorias que comienzan con un $\nearrow$ . Lo que queda son caminos que comienzan con un paso horizontal. Pero en ese caso, lo que sigue es un camino legal de longitud $n-1$ . Por lo tanto, la ecuación real es $$ M_n=\;\;(\to, M_{n-1})\;\;+\;\;\bigcup_{k=0}^{n-2}(\nearrow ,M_k,\searrow, M_{n-2-k}) $$

En combinación con el caso base $M_0=1$ esto se traduce en la ecuación de la función generadora $$ M(x) = 1+xM(x)+x^2M(x)^2. $$