Caminos de motzkin y coeficiente trinomial central.

Question

Deje que$ a_n $ sea el coeficiente de$ X^n $ en el polinomio:$ (1+X+X^2)^n $.

Me gustaría probar que$ a_n=\sum\limits_{k=0}^{k=\lfloor n/2\rfloor} \frac{n!}{(k!)^2(n-2k)!}$ es el número de rutas Motzkin que unen$ (0,0) $ a$ (n,0) $. ¿Cómo puedo encontrar una solución (utilizando combinatoria, supongo)?

Answer 1

La fórmula para $a_n$ no es igual a el número de Motzkin caminos que conectan $(0,0)$ a $(n,0)$. Por ejemplo, para $n = 4$ debería ser $9$, mientras que la fórmula da $13$.

Si estabas buscando para comprobar que $a_{n}=\sum_{k=0}^{k=\lfloor{n/2}\rfloor} \frac{n!}{(k!)^2(n-2k)!}$ es el coeficiente de $X^n$ en $(1+X+X^2)^n$, entonces mi anterior explicación no tiene. Para cada una de las $k$, sumando el cuenta el número de maneras de obtener un factor de $X^n$ tomando $k$ veces $1$, $n - 2k$ veces $X$ e $k$ veces $X^2$. Sumando sobre todos los $k \leq n/2$, entonces usted puede obtener todos los términos que contribuyen a que el coeficiente de $X^n$.

Si por el contrario estás buscando fórmulas de Motzkin números, entonces Wolfram MathWorld y OEIS:A001006 debe darle un montón de (correcto) fórmulas. Sin embargo, el que dio no trabajar.

---

A continuación es una prueba de la fórmula, que anon se menciona en los comentarios.

Teorema de La cantidad de Motzkin rutas de $(0,0)$ a $(n,0)$ está dado por $$a_n = \sum_{k=0}^{[n/2]}\frac{n!}{k!(k+1)!(n-2k)!} = \frac{1}{n+1} \sum_{k=0}^{[n/2]} \binom{n+1}{k,k+1,n-2k}$$

La prueba: La prueba es análoga a la prueba de la fórmula de los números de catalán (en particular la segunda prueba). Primero nos cuentan todos los caminos de $(0,0)$ a $(n,0)$ que puede caer por debajo del eje (denotado por $b_n$), luego de restar todas las rutas que, de hecho, cruz del eje (denotado por $c_n$), para finalmente obtener el número deseado $a_n = b_n - c_n$.

Lema 1: El número total de rutas de $(0,0)$ a $(n,0)$ es

$$b_n = \sum_{k=0}^{[n/2]}\frac{n!}{k!k!(n-2k)!} = \sum_{k=0}^{[n/2]} \binom{n}{k,k,n-2k}$$

Prueba: Cualquier ruta de acceso puede ser creada por la primera selección del número de downmoves ( $k$ ) y, a continuación, decidir en cual de las $n$ posiciones que se mueven arriba y abajo. Esto significa que hemos de partición de la $n$ en tres grupos de tamaño $k$ (subir), $k$ (mover hacia abajo) y $n - 2k$ (movimiento horizontal). Suma sobre todos los valores de $k$ obtenemos el resultado.

Lema 2: El número de caminos de $(0,0)$ a $(n,0)$ cruzar el eje es

$$c_n = \sum_{k=0}^{[n/2]}\frac{n!}{(k-1)!(k+1)!(n-2k)!} = \sum_{k=0}^{[n/2]} \binom{n}{k-1,k+1,n-2k}$$

Prueba: Aquí se utiliza un argumento similar como en la Wikipedia. Si un camino que cruza por debajo del eje, entonces debe hacerlo por primera vez. Después de este punto, estamos en $(i,-1)$. Ahora voltear la parte restante de la ruta, es decir, en movimiento vuelve a moverse hacia abajo y se mueve hacia abajo se convierte en movimiento de arriba. Esta volcó en la ruta terminará en $(n,-2)$ en lugar de $(n,0)$. De hecho, hay una correspondencia uno a uno entre estos volteado caminos y rutas de acceso de $(0,0)$ a $(n,-2)$. Por un razonamiento similar, rutas de acceso puede ser construido mediante la selección de una $k$, y disminuyendo el $k+1$ veces y hasta $k-1$ veces. Esto da el resultado.

Ahora completa la prueba del teorema.

$$\begin{array}{rcl} a_n &=& b_n - c_n \\ &=& \sum_{k=0}^{[n/2]}\frac{n!}{k!k!(n-2k)!} - \sum_{k=0}^{[n/2]}\frac{n!}{(k-1)!(k+1)!(n-2k)!} \\ &=& \sum_{k=0}^{[n/2]} \frac{n!}{(k-1)!k!(n-2k)!} \left(\frac{1}{k} - \frac{1}{k+1}\right) \\ &=& \sum_{k=0}^{[n/2]} \frac{n!}{(k-1)!k!(n-2k)!} \left(\frac{1}{k(k+1)}\right) \\ &=& \sum_{k=0}^{[n/2]} \frac{n!}{k!(k+1)!(n-2k)!} \\ &=& \frac{1}{n+1} \sum_{k=0}^{[n/2]} \binom{n+1}{k,k+1,n-2k} \end{array}$$