TAOCP 5.1.1 Exercise 9
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'_k\) is the position of \(k\) in \(a\).
Exercise 9. [M21] Prove that the permutation $a_1 a_2 \ldots a_n$ is an involution (that is, its own inverse) if and only if $b_j = C_j$ for $1 \le j \le n$.
Verified: yes
Solve time: 22m
Solution
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'k) is the position of (k) in (a). Equivalently, (a'{a_j}=j) and (a{a'_j}=j) for all (j).
The inversion table (b_1 b_2 \ldots b_n) of (a) is defined by [ b_j = \text{number of } i < a'_j \text{ such that } a_i > j. ] (These are the elements to the left of (j) that are greater than (j).)
From Exercise 7, (c_j) is the number of elements to the right of (j) that are less than (j). Then (C_j = c_{a_j}). Since (a_j) occupies position (j), the elements to its right are (a_k) with (k>j). Hence [ C_j = \bigl|{, k > j \mid a_k < a_j ,}\bigr|. ] For each such (k) set (i = a_k). Then (i < a_j) and the position of (i) is (a'_i = k); the condition (k>j) becomes (a'_i > j). Thus the set is in bijection with [ {, i < a_j \mid a'_i > j ,}, ] so [ C_j = \bigl|{, i < a_j \mid a'_i > j ,}\bigr|. ]
Now consider the inverse permutation (a'). Its inversion table (b'_1 b'_2 \ldots b'_n) is, by definition, [ b'_j = \text{number of elements to the left of } j \text{ in } a' \text{ that are greater than } j. ] In (a'), the value (j) appears at position (a_j) because (a'_k = j \iff a_j = k). Therefore the elements to the left of (j) in (a') are exactly those at indices (i < a_j), and their values are (a'_i). Hence [ b'_j = \bigl|{, i < a_j \mid a'_i > j ,}\bigr| = C_j. ]
The hypothesis “(b_j = C_j) for all (j)” is therefore equivalent to “(b_j = b'_j) for all (j)”, i.e., the inversion tables of (a) and (a') are identical.
The text (Section 5.1.1) states that an inversion table uniquely determines the corresponding permutation - one reconstructs the permutation by successively placing (n, n-1, \ldots, 1) according to the table. Hence identical inversion tables imply (a = a'), which means (a) is an involution.
Conversely, if (a) is an involution then (a = a'), so their inversion tables coincide, giving (b_j = b'_j = C_j) for all (j).
Thus the permutation (a_1 a_2 \ldots a_n) is an involution if and only if (b_j = C_j) for (1 \le j \le n).
∎