Let \(\sigma \in S_n\). The pair \((i,j)\) gives an
*inversion* of \(\sigma\) if
\(i \lt j\)
and \(\sigma(i) \gt \sigma(j)\).
(This should not be confused with the inverse permutation discussed above.)

The total number of inversions of \(\sigma\) is denoted by \(\text{#inv}(\sigma)\).

The identity permutation has no inversions because for every pair \((i,j)\) with \(i \lt j\), \(\sigma(i) = i \lt j = \sigma(j)\). For example, one can see that there are no inversions of the identity permuation from \(S_4\): \(\begin{pmatrix} 1 & 2 & 3 &4 \\ 1 & 2 & 3 &4 \end{pmatrix}\).

Consider \(\sigma = \begin{pmatrix} 1& 2&3\\ 3&1 &2\end{pmatrix}\). The pair \((1,2)\) is an inversion of \(\sigma\) because with \(i = 1\) and \(j = 2\), we have \(i \lt j\) and \(\sigma(i) = 3 \gt 1 = \sigma(j)\). The remaining inversion is given by the pair \((1,3)\). Thus \(\text{#inv}(\sigma) = 2\).

Let \(\sigma \in S_n\) be such that there exist \(i,j \in \{1,\ldots, n\}\), \(i \lt j\) such that \(\sigma(i) = j\), \(\sigma(j) = i\), and \(\sigma(k) = k\) for all \(k \in \{1,\ldots,i-1,i+1,\ldots,j-1,j+1,\ldots,n \}.\) In other words, \(\sigma\) only swaps \(i\) and \(j\). We want to determine \(\text{#inv}(\sigma)\).

Note that for each \(k = i+1,\ldots,j-1\), \((i,k)\) is an inversion because \(i \lt k\) and \(\sigma(i) = j \gt k = \sigma(k)\).

Also, for each \(k = i+1,\ldots,j-1)\), \((k,j)\) is an inversion because \(k \lt j\) and \(\sigma(j) = i \gt k = \sigma(k)\).

Finally, the remaining inversion is \((i,j)\). Thus, \(\text{#inv}(\sigma) = 2(j-1-(i+1)+1) + 1 = 2(j-i)-1\), which is always odd.

For example, the inversions of \(\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 &2 & 5 \end{pmatrix}\) are \((2,3)\), \((3,4)\), and \((2,4)\).

For each of the following permutations, give the number of inversions and the inverse permutation.

\(\begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 3 & 2 & 4\end{pmatrix}\)

\(\begin{pmatrix} 1 & 2 & 3 & 4\\ 4& 3 & 2 & 1\end{pmatrix}\)

\(\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 1 & 4 & 2 &3\end{pmatrix}\)