8
$\begingroup$

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!

  • 0
    Unimportant note: what you write $[j>k]$ is also written (more usually?) as $u(j-k-1)$, where $u(\cdot)$ is the unit step (or Heaviside) function2012-06-01
  • 1
    Which is "more usual" depends on what branch of mathematics you are doing.2012-06-01
  • 1
    @leonbloy I knew the notation from *Concrete Mathematics* and *The Art of Computer Programming* and here's another reference: http://en.wikipedia.org/wiki/Iverson_bracket2012-06-01
  • 0
    Yes, I'm not objecting to it, just pointing the alternative in case someone find it easier to deal with. BTW "houses" or "horses" ? (and "students"?). BTW2: Are you interested in solving this recursion or just in solving analitically the original problem?2012-06-01
  • 0
    @GEdgar More details? I can't get your idea.2012-06-01
  • 0
    @Frank: "leonboy" said using Heaviside unit step function is **more usual** than Iverson-Knuth bracket $[j>k]$. While that may be true in certain branches of mathematics, it is false in others.2012-06-01
  • 0
    @leonbloy The solution to the recurrence is what I'm interested in even though it's unneccessary for the origin problem (and the origin one can be solved through the recurrence which gives a polynomial algorithm). Because of my bad English, I can't describe why $f_{j,k}^{(l)}$ is introduced.2012-06-01
  • 0
    @leonbloy The bug of ambiguity between *horse* and *house* is fixed.2012-06-01

2 Answers 2

1

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).

  • 0
    Yeah, it's really linear probing. I don't know it's an open problem, but what about my recurrence? It seems that the recurrence can be solved.2012-06-04
  • 0
    The recurrence is related to Lemma 2 in *Knuth's first analysis*. Am I right?2012-06-04
0

Let the known solution at $$j=l$$ define the generating function $$g^l(z)\equiv \sum_{k\ge 0} j^{k-1}(j-k)z^k = \frac{1-(j+1)z}{(1-jz)^2}.$$ For larger $j$ the sequence of $k$ is given by repeated/recursive application of a binomial transform, where the associated effect on the generating function is $$g^{j}(z) = \frac{1}{1-z}g^{j-1}(\frac{z}{1-z})$$. See for example equation (58) in http://www.mpia.de/~mathar/public/mathar20071126.pdf This effectively leads to the generating function $$g^{l+i}(z) = \frac{1-(i+1+j)z}{[1-(i+j)z]^2},\, i\ge 0.$$ The partial fraction decomposition of this is $$g^{l+i}(z) = \frac{j+i+1}{j+i}\frac{1}{1-(i+j)z}-\frac{1}{j+i}\frac{1}{[1-(j+i)z]^2}.$$ The result has the same format at the one obtained for $j=l$ just substituting $j\to i+j$. So from that it appears $f_{j+i,k}^{(l)} = (i+j)^{k-1}(i+j-k)$. This is just a rough analysis which does not yet take into account that the generating function should be truncated at $k=j$ instead extending to infinity.