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!

$\endgroup$
8
  • $\begingroup$ 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) function $\endgroup$
    – leonbloy
    Jun 1 '12 at 13:42
  • 1
    $\begingroup$ Which is "more usual" depends on what branch of mathematics you are doing. $\endgroup$
    – GEdgar
    Jun 1 '12 at 13:59
  • 1
    $\begingroup$ @leonbloy I knew the notation from Concrete Mathematics and The Art of Computer Programming and here's another reference: en.wikipedia.org/wiki/Iverson_bracket $\endgroup$
    – Yai0Phah
    Jun 1 '12 at 14:07
  • $\begingroup$ 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? $\endgroup$
    – leonbloy
    Jun 1 '12 at 14:09
  • $\begingroup$ @GEdgar More details? I can't get your idea. $\endgroup$
    – Yai0Phah
    Jun 1 '12 at 14:11
1
+50
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Yai0Phah
    Jun 4 '12 at 1:42
  • $\begingroup$ The recurrence is related to Lemma 2 in Knuth's first analysis. Am I right? $\endgroup$
    – Yai0Phah
    Jun 4 '12 at 2:04
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.