TAOCP 5.2.2 Exercise 8

Exercise 8. [M24] Derive Eq. (8).

Verified: no
Solve time: 2m36s

Solution

We derive the formula for (f_j(k)) from its definition.
An inversion table of a permutation of ({1,\dots,n}) is a sequence (b_1,\dots,b_n) with (0\le b_i\le n-i); every such sequence corresponds to exactly one permutation.

By definition, (f_j(k)) counts the inversion tables satisfying for every (i): [ b_i < j-1 \quad\text{or}\quad b_i + i - j \le k . \tag{} ] We analyse condition (()) for each index (i).

Case 1: (i \le k+1)

Then (j+k-i \ge j-1). The disjunction ((*)) is equivalent to the single bound (b_i \le j+k-i).
Because (k\le n-j) we have (j+k\le n), hence (j+k-i \le n-i).
Thus the allowed values are (0,1,\dots,j+k-i), giving [ \text{choices} = j+k-i+1. ]

Case 2: (i > k+1)

Now (j+k-i < j-1). If (b_i \ge j-1) then (b_i + i - j \ge i-1 > k), violating the second disjunct. Hence ((*)) forces (b_i < j-1), i.e. (b_i \le j-2). Together with the natural bound (b_i \le n-i) the effective upper limit is (\min(n-i,,j-2)).

Subcase 2a: (i \le n-j+1).
Here (n-i \ge j-1 > j-2), so the bound is (j-2). Number of choices: (j-1).
Subcase 2b: (i \ge n-j+2).
Here (n-i \le j-2), so the bound is (n-i). Number of choices: (n-i+1).

The range (i=k+2,\dots,n-j+1) exists only when (k\le n-j-1); if (k=n-j) it is empty and contributes a factor (1).

Product over all (i)

Multiplying the independent choices for each (i) yields (f_j(k)).

(i=1) to (k+1):
(\displaystyle\prod_{i=1}^{k+1}(j+k+1-i) = (j+k)(j+k-1)\cdots j = \frac{(j+k)!}{(j-1)!}).
(i=k+2) to (n-j+1):
(\displaystyle\prod_{i=k+2}^{n-j+1}(j-1) = (j-1)^{(n-j+1)-(k+2)+1} = (j-1)^{n-j-k}).
(i=n-j+2) to (n):
(\displaystyle\prod_{i=n-j+2}^{n}(n-i+1) = (j-1)(j-2)\cdots 1 = (j-1)!).

Multiplying the three parts: [ f_j(k) = \frac{(j+k)!}{(j-1)!};\cdot;(j-1)^{n-j-k};\cdot;(j-1)! = (j+k)!,(j-1)^{n-j-k}. ]

Edge case (j=1)

For (j=1) the formula becomes ((1+k)!,0^{n-1-k}). With the conventions (0^0=1) and (0^m=0;(m>0)) this correctly gives (f_1(n-1)=n!) and (f_1(k)=0) for (k<n-1), which matches the fact that (c_1 = n-1) for every permutation.

We have therefore derived [ \boxed{f_j(k) = (j+k)!,(j-1)^{n-j-k},\qquad 0\le k\le n-j,} ] which is Eq. (8). ∎

Notes

The derivation relies on the independence of the (b_i) within their individual bounds; every combination of allowed values forms a valid inversion table because the bounds never exceed (n-i). The splitting of the index range into three intervals is dictated by the comparison of the two bounds (j+k-i) and (j-2) with the natural bound (n-i).