Inversions

Notes

Inversions are an important concept when discussing Permutations and Combinatorics.

An inversion is a pair of items (not necessarily neighbors) that are out of order in a permutation.

If we have a set of items, for example the integers 1, 2, 3, 4, 5, a permutation is an arrangement of those items in a particular order. This is typically written with two line notation - the first line indicating the natural order of the items, the second indicating their arrangement in the permutation.

$ a = \bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 5 & 3 & 2 & 4 \end{smallmatrix}\bigr) $

But writing the second row only is more convenient, so we will write the second row by itself going forward.

Definition

An inversion is defined as a pair of items that are out of order in a permutation. These items do not need to be neighbors, which means we must consider every pairwise combination of elements. Consider the example:

$ 1 \, 5 \, 3 \, 2 \, 4 $

We can build a table of all inversions:

i j  inversion? (1=yes, 0=no)
------------------------------
1 5  0
1 3  0
1 2  0
1 4  0
5 3  1
5 2  1
5 4  1
3 2  1
3 4  0
2 4  0

total: 4

Maximum Number of Inversions

From consideration of the definition of an inversion, we can see that the maximum number of inversions occurs when the entire array is reversed, so that every pairwise combination is an inversion.

This is usually accompanied by an iteration structure like this (note that j starts at i):

for (i = 0; i < n; i++ ){ 
    for (j = i; j < n; j++ ){
        ...
    }
}

Mathematically, this is equivalent to the sum:

$ \sum_{i=0}^{n} \sum_{j=i}^{n} ... $

If we use 1 as the expression in the sum and shift the index we can combine the sums like so:

$ \sum_{i=0}^{n} \sum_{j=i+1}^{n} 1 = \sum_{i=0}^{n} \sum_{j=0}^{i-1} 1 = \sum_{i=0}^{n} i-1 $

Now we use the famous formula for the sum of the first n integers, where n = i - 1, to get:

$ \sum_{i=0}^{n} \sum_{j+1}^{n} = \dfrac{ (n)(n-1) }{2} $

Related

• Inversions
• Permutations
• Rubiks Cube/Permutations
• Combinatorics