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

Number of Inversions

Suppose P is a permutation, and Pr is the reversal of that permutation.

Then we can show that the total number of inversions in both P and Pr is

${\dfrac {n(n-1)}{2}}$

Suppose we have a permutation with n items. Now we add an additional item at the end.

The reversal for the old permutation got (n)(n-1) inversions.

The (n+1)th item adds n new inversions, which are (n+1,n), (n+1,n-1),(n+1,1).

Therefore we have

${\dfrac {n(n-1)}{2}}+n={\dfrac {n^{2}-n+2n}{2}}={\dfrac {n(n+1)}{2}}$

Expected Number of Inversions

Take the minimum and maximum number of inversions, which are 0 and ${\dfrac {n(n-1)}{2}}$ .

If we assume that all inversions are uniformly distributed, the number of inversions on average will be the mean of the min and max, which is

${\dfrac {0+{\frac {n(n-1)}{2}}}{2}}={\dfrac {n(n-1)}{4}}$

Cards

We can apply this idea to a pack of 52 Cards, although in the case of a pack of cards we have to account for duplicates (or assign an arbitrary ranking for suits to break ties).

Flags