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)$$.

### Examples

1. 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}$$.

2. 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$$.

3. 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)$$.

4. 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)$$.

## Exercises

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

1. $$\begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 3 & 2 & 4\end{pmatrix}$$

2. $$\begin{pmatrix} 1 & 2 & 3 & 4\\ 4& 3 & 2 & 1\end{pmatrix}$$

3. $$\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 1 & 4 & 2 &3\end{pmatrix}$$