Even and Odd Permutations

Recall from the Inversions of Permutations page that if $A = \{1, 2, ..., n \}$ is a finite $n$-element set of positive integers then an inversion of the $n$-permutation $(x_1, x_2, ..., x_n)$ occurs when $j < k$ and $x_j > x_k$. We saw that the minimum number of inversions of an $n$-permutation is $0$ and the maximum number of $n$-permutations is $\sum_{i=1}^{n-1} i = \frac{(n-1)n}{2} = \frac{n^2 - n}{2}$.

We will now look further into counting the total number of inversions in an $n$-permutation. The total number of inversions in an $n$-permutation will determine whether we define the permutation to be either even or odd.

Definition: If $A = \{1, 2, ..., n \}$ is a finite $n$-element set of positive integers then the $n$-permutation $(x_1, x_2, ..., x_n)$ is said to be an Even Permutation of elements in $A$ if the number of inversions in this permutation is even. Similarly, $(x_1, x_2, ..., x_n)$ is said to be an Odd Permutation of elements in $A$ if the number of inversions in this permutation is odd.

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

(1)

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

The pair $(2, 1)$ and $(4, 3)$ are the only inversions in this $4$-permutation and there are precisely $2$ of these inversions and so $(2, 1, 4, 3)$ is an even permutation.

(2)

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

The pairs $(4, 1)$, $(4, 2)$, and $(4, 3)$ are the only inversions in this $4$-permutation and this time there are $3$ of these inversions and so $(4, 1, 2, 3)$ is an odd permutation.