Inversions of Permutations

Definition: If $A = \{1, 2, ..., n \}$ is a finite $n$-element set of positive integers and $(x_1, x_2, ..., x_n)$ is an $n$-permutation of the elements in $A$ then the pair $(x_j, x_k)$ is an Inversion of this permutation if $j < k$ and $x_j > x_k$.

For example, consider the following $4$-permutation of elements in $A = \{1, 2, 3, 4, 5 \}$:

(1)

\begin{align} \quad (4, 2, 3, 1) \end{align}

The pair $(4, 2)$ is an inversion because the number $4$ appears before the number $2$ and $4 > 2$. The pairs $(4, 3)$, $(4, 1)$, and $(3, 1)$ are also inversions of this $4$-permutation.

One defining characteristic of a specific permutation is the number of inversions a certain permutation has. The following theorem will tell us that a $n$-permutation can have at minimum $0$ inversions and at maximum $(n - 1)!$ inversions.

Theorem 1: If $A = \{ 1, 2, ..., n \}$ is a finite $n$-element set then any permutation $(x_1, x_2, ..., x_n)$ of elements from $A$ has at minimum $0$ inversions or at maximum $\sum_{i=1}^{n-1} i = \frac{(n-1)(n)}{2} = \frac{n^2 - n}{2}$ inversions.

• Proof: Consider the $n$-permutation $(x_1, x_2, ..., x_n) = (1, 2, ..., n )$. For every pair $(x_j, x_k)$ and for $j, k \in \{ 1, 2, ..., n \}$ and $j < k$ we have that $x_j \not > x_k$ and so no inversions for this permutation exist.

• Now consider the $n$-permutation $(y_1, y_2, ..., y_n) = (n, n-1, ..., 2, 1)$. For every pair $(y_j, y_k)$ and for $j, k \in \{1, 2, .., n \}$ and $j < k$ we have that $y_j > y_k$ and so every pair is an inversion. We will now show that $(n - 1)!$ pairs exist for this permutation. We start by constructing the possible ordered pairs of this permutation starting with the first element being $y_1$, i.e., $(y_1, y_k)$. Since $1 < k$ for all $k \in \{2, 3, ..., n \}$ we have that $n - 1$ pairs exist. We then construct the possible ordered pairs of this permutation starting with the first element being $y_2$, i.e. $(y_2, y_k)$. Since $2 < k$ for all $k \in \{3, 4, ..., n \}$ we have that $n - 2$ pairs exist. We continue in this process and construct the possible ordered pairs of this permutation starting with the first element being $y_{n-1}$, i.e, $(y_{n-1}, y_k)$. Since $n - 1 < k$ for all $k \in \{ n \}$ we have that $1$ pair exist. By the addition principle we have that the total number of pairs and hence inversions for the permutation $(n, n-1, ..., 2, 1)$ is:

(2)

\begin{align} \quad \sum_{i=1}^{n-1} i = \frac{(n - 1)n}{2} = \frac{n^2 - n}{2} \quad \blacksquare \end{align}