Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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 –  leonbloy Jun 1 '12 at 13:42
1  
Which is "more usual" depends on what branch of mathematics you are doing. –  GEdgar Jun 1 '12 at 13:59
1  
@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 –  Frank Science Jun 1 '12 at 14:07
    
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? –  leonbloy Jun 1 '12 at 14:09
    
@GEdgar More details? I can't get your idea. –  Frank Science Jun 1 '12 at 14:11
show 3 more comments

1 Answer

up vote 1 down vote accepted
+50

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

share|improve this answer
    
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. –  Frank Science Jun 4 '12 at 1:42
    
Thanks. I will first read some of these articles. –  Frank Science Jun 4 '12 at 1:48
    
The recurrence is related to Lemma 2 in Knuth's first analysis. Am I right? –  Frank Science Jun 4 '12 at 2:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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