My question is, how can the inverse of $5 9 1 8 2 6 4 7 3$ be $3 5 9 7 1 6 8 4 2$? At first glance, 1 and 2 are both less than 3, for example, which seems to conflict with the instruction "then sorting the columns into increasing order". Is this not a total order over the natural numbers?
The reader should not confuse inversions of a permutation with the inverse of a permutation. Recall that we can write a permutation in two-line form
$$\left(\begin{matrix}
1 & 2 & 3 & \cdots & n\\
a_1 & a_2 & a_3 & \cdots & a_n
\end{matrix}\right)$$
the inverse $a'^1a'^2a'^3 … a'^n$ of this permutation is the permutation obtained by interchanging the two rows and then sorting the columns into increasing order of the new top row:
$$\left(\begin{matrix}
a_1 & a_2 & a_3 & \cdots & n\\
1 & 2 & 3 & \cdots & n
\end{matrix}\right)=\left(\begin{matrix}
1 & 2 & 3 & \cdots & n\\
a'_1 & a'_2 & a'_3 & \cdots & a'_n
\end{matrix}\right) $$
For example, the inverse of $5 9 1 8 2 6 4 7 3$ is $3 5 9 7 1 6 8 4 2$, since$$\left(\begin{matrix}
5 & 9 & 1 & 8 & 2 & 6 & 4 & 7 & 3\\
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9
\end{matrix}\right)=\left(\begin{matrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
3 & 5 & 9 & 7 &1 & 6 & 8 & 4 & 2
\end{matrix}\right) $$
— Knuth, Donald. The Art of Computer Programming: Sorting and Searching. Vol. 3, Second Edition.
Best Answer
Given permutation is: 591826473 To get the inverse of this first write down the position of 1 It is in the 3rd position . SO inverse starts as "3 ...". Next locate 2 in the permutation. It is in the 5th position. So inverse expands to "35...." Similarly go on chasing 3,4 etc and note down their positions and build the inverse permutation.