Solve the recurrence \[ 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{cases} \] for all nonnegative integer $k$ and postive integers $j$, $l$, where
\[ [P] = \begin{cases} 1, &\qquad \hbox{if $P$ is true} \\ 0, &\qquad \hbox{otherwise} \end{cases} \]
is Iverson bracket, see Wikipedia. For example, $[2 < 3] = 1; [2 > 3] = 0$
The problem is introduced from a programming problem from URAL. I'm trying to find a closed form solution for the problem (notice that $f_{j,k}^{(l)}$ is the number of arrangements of $j$ horses and $k$ students in which the last horse is empty and the adjacent $l$ horses are not all occupied).
Here I want to show an algebraic way, to obtain $f_{j,k}^{(l)} = [j>k] j^{k-1}(j-k), \qquad j=l$ which I got through combinatorial interpretation, that I think helpful to solve the recurrence of $f_{j,k}^{(l)}$. In fact, $[j>k] j^{k-1}(j-k)$ is the solution to the following recurrence:
\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*}
Notice that the recurrence of $g$ is similiar with that of $f^{(l)}$. It seems to be as strange as the recurrence of $f^{(l)}$, but it isn't too messy.
Let's solve it by hand. First assume that
\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*}
We have $g_{1,k}^* = g_{1,k}$ for $0 \le k \le 1$. Now let's consider the exponential generating function for $g_{j,k}^*$: $\hat G_j^*(z) = \sum_{k \ge 0} g_{j,k}^* z^k/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*} and for $j > 1$, \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*} so $\hat G_j^*(z) = (1-z)e^{jz}$, and we get $g_{j,k}^* = j^{k-1}(j-k)$, and $g_{k,k}^* = g_{k,k} = 0$ whenever $k \ge 1$.
Now it's easy to prove $g_{j,k} = g_{j,k}^*$ for $0 \le k \le j$ by induction on $j$.
Can we solve $f_{j,k}^{(l)}$ like this? More precisely, extend some zeros of $f_{j,k}^{(l)}$ to nonzeros to eliminate the awful factor $[j > k + 1]$ in recurrence, solve it and prove that the nonzeros of $f_{j,k}^{(l)}$ keeps its value when extending?
Thanks for your help!
The usual presentation for this problem is determining the expected running time in terms of the load and the size of the table of inserting into a hash table with linear probing. Knuth himself was interested in this problem (Notes on "Open" Addressing, 1963).