Resolver la recurrencia \[ f_{j,k}^{(l)} = \begin{cases} \left[j>k\right] j^{k-1}(j-k), &\qquad j=l \\ \\ \left[j>k+1\right] \sum_t \binom k t f_{j-1,k-t}^{(l)}, &\qquad j>l \end{casos} \] para todo entero no negativo $k$ y positivos enteros $j$, $l$, donde
\[ [P] = \begin{cases} 1, &\qquad \hbox{if %#%#% is true} \\ 0, &\qquad \hbox{otherwise} \end{casos} \]
es Iverson soporte, consulte la Wikipedia. Por ejemplo, $P$
El problema es introducido a partir de un problema de programación de los URALES. Estoy tratando de encontrar una solución de forma cerrada para el problema (aviso que $[2 < 3] = 1; [2 > 3] = 0$ es el número de arreglos de $f_{j,k}^{(l)}$ caballos y $j$ estudiantes en la que el último caballo está vacío y el adyacente $k$ caballos no están todos ocupados).
Aquí quiero mostrar una expresión algebraica manera, para obtener el $l$ que llegué a través de la combinatoria de interpretación, que creo útiles para resolver la recurrencia de $f_{j,k}^{(l)} = [j>k] j^{k-1}(j-k), \qquad j=l$. De hecho, $f_{j,k}^{(l)}$ es la solución a la siguiente recurrencia:
\begin{align*} g_{1,k} &= \left[k \le 1\right] (1 - k), \qquad k \ge 0 \\ g_{j,k} &= \left[k < j\right] \sum_t \binom k t g_{j-1,k-t}, \qquad j > 1, k \ge 0 \end{align*}
Observe que la recurrencia de la $[j>k] j^{k-1}(j-k)$ es comparable con la de $g$. Parece ser tan extraño como la recurrencia de $f^{(l)}$, pero no es demasiado complicado.
Vamos a resolver a mano. Primero suponga que
\begin{align*} g_{1,k}^* &= 1 - k, \qquad k \ge 0 \\ g_{j,k}^* &= \sum_t \binom k t g_{j-1,k-t}, \qquad j > 1, k \ge 0 \end{align*}
Tenemos $f^{(l)}$$g_{1,k}^* = g_{1,k}$. Ahora vamos a considerar la exponencial de generación de función para $0 \le k \le 1$: $g_{j,k}^*$. \begin{align*} \hat G_1^*(z) &= \sum_{k \ge 0} \frac{(1-k)z^k}{k!} \\ &= \sum_{k \ge 0} \left(\frac{z^k}{k!} - \frac{kz^k}{k!}\right) \\ &= \sum_{k \ge 0} \frac{z^k}{k!} - \sum_{k \ge 0} \frac{z^{k+1}}{k!} \\ &= (1-z)e^z \end{align*} y para $\hat G_j^*(z) = \sum_{k \ge 0} g_{j,k}^* z^k/k!$, \begin{align*} \hat G_j^*(z) &= \sum_{k \ge 0} \sum_{0 \le t \le k} \frac{g_{j-1,k-t}^*z^k}{t!(k-t)!} \\ &= \sum_{t \ge 0} \frac{z^t}{t!} \sum_{k \ge t} \frac{g_{j-1,k-t}^*z^{k-t}}{(k-t)!} \\ &= \sum_{t \ge 0} \frac{z^t}{t!} \sum_{k \ge 0} \frac{g_{j-1,k}^*z^k}{k!} \\ &= e^z \hat G_{j-1}^*(z) \end{align*} por lo $j > 1$, y llegamos $\hat G_j^*(z) = (1-z)e^{jz}$, e $g_{j,k}^* = j^{k-1}(j-k)$ siempre $g_{k,k}^* = g_{k,k} = 0$.
Ahora, es fácil demostrar $k \ge 1$ $g_{j,k} = g_{j,k}^*$ por inducción en $0 \le k \le j$.
Podemos solucionar $j$ como esta? Más precisamente, ampliar algunos ceros de $f_{j,k}^{(l)}$ a nonzeros para eliminar la horrible factor de $f_{j,k}^{(l)}$ en la recurrencia, resolverlo y demostrar que el nonzeros de $[j > k + 1]$ mantiene su valor a la hora de ampliar?
Gracias por su ayuda!
