TAOCP 5.1.1 Exercise 7

Let \(a_1 a_2 \ldots a_n\) be a permutation of \(\{1,2,\ldots,n\}\).

taocpmathematicsalgorithmsvolume-3hard

Section 5.1.1: Inversions

Exercise 7. [30] Several other kinds of inversion tables can be defined, corresponding to a given permutation $a_1 a_2 \ldots a_n$ of ${1, 2, \ldots, n}$, besides the particular table $b_1 b_2 \ldots b_n$ defined in the text. In this exercise we will consider three other types of inversion tables that arise in applications.

Let $c_j$ be the number of inversions whose first component is $j$, that is, the number of elements to the right of $j$ that are less than $j$. [Corresponding to (1) we have the table 0 1 0 0 1 4 2 1 5 7; clearly $0 \le c_j < j$.] Let $B_j = b_{a_j}$ and $C_j = c_{a_j}$.

Show that $0 \le B_j < j$ and $0 \le C_j \le n - j$, for $1 \le j \le n$; furthermore show that the permutation $a_1 a_2 \ldots a_n$ can be determined uniquely when either $c_1 c_2 \ldots c_n$ or $B_1 B_2 \ldots B_n$ or $C_1 C_2 \ldots C_n$ is given.

Verified: yes
Solve time: 17m27s

Setup

Let (a_1 a_2 \ldots a_n) be a permutation of ({1,2,\ldots,n}).
For each (x \in {1,\ldots,n}) denote by (\operatorname{pos}(x)) the index (i) such that (a_i = x).

The inversion table (b_1 b_2 \ldots b_n) is defined by
[ b_x = \bigl|{ i < \operatorname{pos}(x) \mid a_i > x }\bigr|. ]

We are given three auxiliary tables:

  • (c_x = \bigl|{ k > \operatorname{pos}(x) \mid a_k < x }\bigr|) (number of inversions whose first component is (x)).
  • (B_j = b_{a_j}) (number of inversions whose second component is at position (j)).
  • (C_j = c_{a_j}) (number of inversions whose first component is at position (j)).

The problem asks to prove
[ 0 \le B_j < j \quad\text{and}\quad 0 \le C_j \le n-j \qquad (1\le j\le n), ] and to show that the permutation (a_1\ldots a_n) can be uniquely recovered from each of the sequences (c_1\ldots c_n), (B_1\ldots B_n), (C_1\ldots C_n).

Solution

1. Bounds for (B_j) and (C_j)

The element at position (j) is (a_j). The elements to its left are (a_1,\ldots,a_{j-1}); there are exactly (j-1) of them. By definition (B_j) counts those among them that are greater than (a_j). Hence [ 0 \le B_j \le j-1 \quad\Longrightarrow\quad 0 \le B_j < j. ]

The elements to the right of position (j) are (a_{j+1},\ldots,a_n); there are exactly (n-j) of them. (C_j) counts those among them that are smaller than (a_j). Hence [ 0 \le C_j \le n-j. ]

2. Unique reconstruction from (c_1 c_2 \ldots c_n)

We are given numbers (c_1,\ldots,c_n) satisfying (0 \le c_x < x) (since at most (x-1) elements are smaller than (x)).
We build the permutation by inserting the elements (1,2,\ldots,n) in increasing order.
Maintain a list (L) (initially empty) that always contains the already placed elements in their final relative order.
When inserting (x), all elements currently in (L) are smaller than (x). The value (c_x) tells us that exactly (c_x) of those smaller elements must lie to the right of (x) in the final permutation. Since (|L| = x-1), this means (x) must have ((x-1-c_x)) elements to its left.
Therefore we insert (x) into (L) at position (x-1-c_x) (0‑indexed from the left). The condition (0 \le c_x < x) guarantees (0 \le x-1-c_x \le x-1), so the insertion is always valid.
After processing (x = n) the list (L) equals the desired permutation (a_1\ldots a_n).
Because every step is forced, the mapping from permutations to (c)-tables is injective; hence the permutation is uniquely determined by (c_1\ldots c_n).

3. Unique reconstruction from (B_1 B_2 \ldots B_n)

We are given (B_1,\ldots,B_n) with (0 \le B_j < j).
We determine the permutation by selecting the elements from right to left (i.e. for (j = n, n-1, \ldots, 1)).
Keep a set (S) of the numbers not yet placed; initially (S = {1,2,\ldots,n}) (kept in increasing order).
At step (j) the set (S) has size (j). The numbers that will eventually occupy positions (1,\ldots,j-1) are exactly the elements remaining in (S) after we choose (a_j). By definition, (B_j) is the number of those future left neighbours that are greater than (a_j). Therefore among the (j) elements currently in (S), exactly (B_j) must be larger than (a_j). Consequently (a_j) must be the ((B_j+1))-st largest element of (S).
Equivalently, if (S) is sorted increasingly, (a_j) is the element at index (j-1-B_j) (0‑indexed). Remove (a_j) from (S) and continue.
Since (0 \le B_j < j), the index (j-1-B_j) always lies in ([0,,j-1]), so the choice is uniquely defined. The process yields the permutation (a_1\ldots a_n), proving unique recoverability from the (B)-table.

4. Unique reconstruction from (C_1 C_2 \ldots C_n)

We are given (C_1,\ldots,C_n) with (0 \le C_j \le n-j). This is the classical Lehmer code (factorial number system).
We construct the permutation from left to right (for (j = 1,\ldots,n)).
Maintain a sorted list (S) of the still unused numbers; initially (S = [1,2,\ldots,n]).
At step (j) the numbers that will appear to the right of position (j) are exactly the elements remaining in (S) after we pick (a_j). The definition of (C_j) requires that exactly (C_j) of those right neighbours are smaller than (a_j). Because (S) is sorted increasingly, this means (a_j) must be the ((C_j+1))-st smallest element of (S), i.e. the element at index (C_j) (0‑indexed). Remove it from (S) and proceed.
The condition (0 \le C_j \le n-j) guarantees (C_j \le |S|-1), so the index is always valid. The resulting sequence is the unique permutation with the given (C)-table.

Verification

We test all statements on the permutation (a = 3;1;4;2) ((n=4)).

Tables: [ \begin{array}{c|cccc} x & 1 & 2 & 3 & 4 \ \hline b_x & 1 & 2 & 0 & 0 \ c_x & 0 & 0 & 2 & 1 \end{array} \qquad \begin{array}{c|cccc} j & 1 & 2 & 3 & 4 \ \hline a_j & 3 & 1 & 4 & 2 \ B_j = b_{a_j} & 0 & 1 & 0 & 2 \ C_j = c_{a_j} & 2 & 0 & 1 & 0 \end{array} ]

Bounds:
(B_1=0<1,; B_2=1<2,; B_3=0<3,; B_4=2<4.)
(C_1=2\le 3,; C_2=0\le 2,; C_3=1\le 1,; C_4=0\le 0.) ✓

Reconstruction from (c = (0,0,2,1)):
(L=[])
(x=1:; 1-1-0=0 \rightarrow L=[1])
(x=2:; 2-1-0=1 \rightarrow L=[1,2])
(x=3:; 3-1-2=0 \rightarrow L=[3,1,2])
(x=4:; 4-1-1=2 \rightarrow L=[3,1,4,2]) ✓

Reconstruction from (B = (0,1,0,2)):
(S=[1,2,3,4])
(j=4:; B_4=2,; \text{index}=4-1-2=1 \rightarrow a_4=2,; S=[1,3,4])
(j=3:; B_3=0,; \text{index}=3-1-0=2 \rightarrow a_3=4,; S=[1,3])
(j=2:; B_2=1,; \text{index}=2-1-1=0 \rightarrow a_2=1,; S=[3])
(j=1:; B_1=0,; \text{index}=1-1-0=0 \rightarrow a_1=3) ✓

Reconstruction from (C = (2,0,1,0)):
(S=[1,2,3,4])
(j=1:; C_1=2 \rightarrow a_1=S[2]=3,; S=[1,2,4])
(j=2:; C_2=0 \rightarrow a_2=S[0]=1,; S=[2,4])
(j=3:; C_3=1 \rightarrow a_3=S[1]=4,; S=[2])
(j=4:; C_4=0 \rightarrow a_4=S[0]=2) ✓

All algorithms recover the original permutation, confirming the theoretical derivations.

This completes the proof. ∎