TAOCP 5.1.1 Exercise 8
We adopt the notation of the text and Exercise 7.
Exercise 8. [M24] Continuing the notation of exercise 7, let $a'_1 a'_2 \ldots a'_n$ be the inverse of the permutation $a_1 a_2 \ldots a_n$, and let the corresponding inversion tables be $b'_1 b'_2 \ldots b'_n$, $c'_1 c'_2 \ldots c'_n$, $B'_1 B'_2 \ldots B'_n$, and $C'_1 C'_2 \ldots C'_n$. Find as many interesting relations as you can between the numbers $a_j$, $b_j$, $c_j$, $B_j$, $C_j$, $a'_j$, $b'_j$, $c'_j$, $B'_j$, $C'_j$.
Verified: yes
Solve time: 24m33s
Solution
We adopt the notation of the text and Exercise 7. Let (a_1 a_2 \ldots a_n) be a permutation of ({1,2,\ldots,n}), and let (a'_1 a'2 \ldots a'n) be its inverse, so that
[
a'{a_j}=j,\qquad a{a'_j}=j \qquad (1\le j\le n).
]
For the original permutation we define
[
\begin{aligned}
b_j &= #{,i<a'j : a_i>j,}, &
c_j &= #{,k>a'j : a_k<j,}, \[2pt]
B_j &= b{a_j} = #{,i
The following relations hold.
1. Cross relations between the tables of (a) and (a')
[ \boxed{b'_j = C_j},\qquad \boxed{c'_j = B_j},\qquad \boxed{B'_j = c_j},\qquad \boxed{C'_j = b_j} \qquad (1\le j\le n). ]
Proof.
(b'_j) counts values (i<a_j) with (a'_i>j). The condition (a'_i>j) means that the position of value (i) in the original permutation is (>j); this is exactly the number of indices (k>j) with (a_k<a_j), which is (C_j). Hence (b'_j=C_j).
(c'_j) counts values (k>a_j) with (a'k<j), i.e. positions (i<j) with (a_i>a_j), which is (B_j).
Then (B'j = b'{a'j} = C{a'j} = c{a{a'j}} = c_j), and (C'j = c'{a'j} = B{a'j} = b{a{a'_j}} = b_j). ∎
2. Position expressed through its own tables
[ \boxed{a'_j = j + b_j - c_j},\qquad \boxed{a_j = j + C_j - B_j} \qquad (1\le j\le n). ]
Proof.
For a fixed value (j), there are (a'_j-1) elements to its left. Among them, (b_j) are larger than (j); the remaining (a'_j-1-b_j) are smaller than (j). The total number of elements smaller than (j) is (j-1), of which (c_j) lie to the right of (j). Hence
[
j-1 = (a'_j-1-b_j) + c_j ;\Longrightarrow; a'_j = j + b_j - c_j.
]
The second formula follows by applying the first to the inverse permutation (using (b'_j=C_j,;c'_j=B_j) from §1) or by an analogous count at position (j). ∎
3. Tables linked by the permutation (a) and its inverse (a')
[ \boxed{b_j = B_{a'j}},\quad \boxed{c_j = C{a'j}},\quad \boxed{B_j = b{a_j}},\quad \boxed{C_j = c_{a_j}}, ] [ \boxed{b'j = B'{a_j}},\quad \boxed{c'j = C'{a_j}},\quad \boxed{B'j = b'{a'_j}},\quad \boxed{C'j = c'{a'_j}}. ]
Proof.
(B_{a'j} = b{a_{a'_j}} = b_j); the others are similar. ∎
4. Bounds (from the definitions and §1)
[ \begin{aligned} 0\le b_j\le n-j,; b_n=0;\qquad & 0\le c_j\le j-1,; c_1=0;\ 0\le B_j\le j-1,; B_1=0;\qquad & 0\le C_j\le n-j,; C_n=0. \end{aligned} ] The same bounds hold for the primed quantities; they are consistent with the cross relations (e.g. (b'_j=C_j\le n-j)).
5. Total number of inversions
Let (I) be the total number of inversions of (a) (which equals that of (a')). Then [ \sum_{j=1}^n b_j = \sum_{j=1}^n c_j = \sum_{j=1}^n B_j = \sum_{j=1}^n C_j = I, ] and the same sums for the primed tables also equal (I).
6. Symmetry
Applying the cross relations of §1 twice returns the original tables: [ b_j = C'_j,\quad c_j = B'_j,\quad B_j = c'_j,\quad C_j = b'_j. ] Consequently, all formulas are symmetric under exchanging ((a,b,c,B,C)) with ((a',b',c',B',C')).
These relations completely describe the algebraic connections among the nine sequences (a_j, b_j, c_j, B_j, C_j, a'_j, b'_j, c'_j, B'_j, C'_j). Every one of them can be verified on the example permutation (5,9,1,8,2,6,4,7,3) given in the text. This completes the proof. ∎