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
    Commented Jun 1, 2012 at 13:42
  • 1
    $\begingroup$ Which is "more usual" depends on what branch of mathematics you are doing. $\endgroup$
    – GEdgar
    Commented Jun 1, 2012 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
    Commented Jun 1, 2012 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
    Commented Jun 1, 2012 at 14:09
  • $\begingroup$ @GEdgar More details? I can't get your idea. $\endgroup$
    – Yai0Phah
    Commented Jun 1, 2012 at 14:11

2 Answers 2

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .