Derivar una relación de recurrencia

Question

El número de secuencias de longitud$n$ consiste en enteros positivos tales que los elementos de apertura y final son$1$ o$2$ y la diferencia absoluta entre cualquier$2$ de elementos consecutivos es$0$ o 1 está dado por$T_{n}$ donde
ps

Además,$$T_{n} = \frac{2n+3}{n+3}T_{n-1} + \frac{3n}{n+3}T_{n-2}\;.$ es$T_{n}$ Número de Motzkin. ¿Cómo derivar la recurrencia anterior del problema dado?

Answer 1

Claramente $T_n$ es el número de secuencias de longitud $n$ de los enteros no negativos cuyos primero y último elementos son en $\{0,1\}$ y cuyos términos consecutivos difieren en la mayoría de las $1$. Intercalando las secuencias entre dos ceros le da las secuencias de $y$-coordenadas de Motzkin caminos de longitud $n+1$, lo $T_n$ es, de hecho,$M_{n+1}$. La recurrencia

$$(n+3)T_n=(2n+3)T_{n-1}+3nT_{n-2}$$

por lo tanto, corresponde a la Motzkin recurrencia

$$(n+2)M_n=(2n+1)M_{n-1}+3(n-1)M_{n-2}\;.\tag{1}$$

Una combinatoria prueba de esto se da en Serge Dulucq & Jean-Guy Penaud, 'Interprétation bijective d'une récurrence des nombres de Motzkin', Matemáticas Discretas $256$ $(2002)$, $671$-$676$. Primero observar que no es un clásico bijection entre Motzkin caminos de longitud $n$ y completa árboles binarios con $n+2$ hojas y $n+1$ nodos internos. Deje $\mathscr{T}_n$ el conjunto de tales árboles. Ahora considere la punta de los árboles, es decir, los árboles con un nodo distinguido. Hay $(n+2)M_n$ formas de seleccionar un árbol de $\mathscr{T}_n$ y punto, una de sus hojas. Hay $(2n+1)M_{n-1}$ formas de seleccionar un árbol de $\mathscr{T}_{n-1}$ y un punto cualquiera de sus nodos. Y hay $(n-1)M_{n-2}$ formas de seleccionar un árbol de $\mathscr{T}_{n-2}$ y el punto de uno de sus nodos internos.

Ahora vamos a $\mathscr{T}_n^\ell$ el conjunto de los árboles obtenidos, señalando una hoja de un árbol en $\mathscr{T}_n$, $\mathscr{T}_n^i$ el conjunto de los obtenidos señalando con un nodo interno de un árbol en $\mathscr{T}_n$, e $\mathscr{T}_n^p$ el conjunto de los obtenidos por señalar cualquier nodo de un árbol en un árbol en $\mathscr{T}_n$. En efecto, los autores presentan un bijection entre el $\mathscr{T}_n^\ell$ $\mathscr{T}_{n-1}^i\cup 3\mathscr{T}_{n-2}^p$ donde $3\mathscr{T}_{n-2}^p$ es distinto de la unión de tres copias de $\mathscr{T}_{n-2}^p$, con lo que se establece $(1)$, y con ella su recurrencia.

La construcción no es terriblemente complicado, pero es un poco largo y complejo a dar aquí en detalle, y los diagramas en el papel de gran ayuda.