# Inversion (discrete mathematics)

A permutation and its inversion set and little-endian factorial number (the latter erroneously called inversion vector)

Inversion is a concept in discrete mathematics to measure how much a sequence is out of its natural order.
An inversion of a permutation is not to be confused with the inverse of a permutation.

## Definitions

An inversion is a pair of places of a permutation where the elements are out of their natural order.

The inversion set of a permutation is the set of all its inversions.
Its potential elements are all pairs of places, which can be arranged in a triangle.

The inversions can also be displayed in the permutation matrix. This technique is called a Rothe diagram:
Usually the entries of the permutation matrix are dots, and the inversions are crosses.
The position of the inversion ${\displaystyle \scriptstyle (i,j)}$ in the matrix is ${\displaystyle \scriptstyle (i,\pi (j))}$. The graphical rule is that a field has a cross, when there is a dot below and to the right of it.

The Lehmer code (${\displaystyle \scriptstyle L}$) is the vector of the row sums of the Rothe diagram. It is the inversion vector of the inverse permutation.

${\displaystyle \scriptstyle L(i)}$ is the number of elements in ${\displaystyle \scriptstyle \pi }$ smaller than ${\displaystyle \scriptstyle \pi (i)}$ after ${\displaystyle \scriptstyle \pi (i)}$. (In other words, ${\displaystyle \scriptstyle L(i)}$ is the number of inversions whose left component is ${\displaystyle \scriptstyle i}$.)
${\displaystyle L(i)=\#\left\{k\mid k>i~\land ~\pi (k)<\pi (i)\right\}}$

The inversion vector (${\displaystyle \scriptstyle V}$) or inversion table is the vector of the column sums of the Rothe diagram. It is the Lehmer code of the inverse permutation.

${\displaystyle \scriptstyle V(i)}$ is the number of elements in ${\displaystyle \scriptstyle \pi }$ greater than ${\displaystyle \scriptstyle i}$ before ${\displaystyle \scriptstyle i}$.
${\displaystyle V(i)=\#\left\{k\mid k>i~\land ~\pi ^{-1}(k)<\pi ^{-1}(i)\right\}}$

The little-endian factorial number (${\displaystyle \scriptstyle F}$) consists of the same numbers as the inversion vector, but in a different order.

${\displaystyle \scriptstyle F(i)}$ is the number of elements in ${\displaystyle \scriptstyle \pi }$ greater than ${\displaystyle \scriptstyle \pi (i)}$ before ${\displaystyle \scriptstyle \pi (i)}$. (In other words, ${\displaystyle \scriptstyle F(i)}$ is the number of inversions whose right component is ${\displaystyle \scriptstyle i}$.)
${\displaystyle F(i)=\#\left\{k\mid k\pi (i)\right\}}$

There is some terminology confusion, due to which in my material the little-endian factorial numbers are often called inversion vectors. This is going to be changed.

The relationship between ${\displaystyle \scriptstyle V}$ and ${\displaystyle \scriptstyle F}$ is:

 ${\displaystyle F~~=~~\pi ~V}$ or ${\displaystyle F(i)~~=~~i~\pi ~V~~=~~V(\pi (i))}$ (compare Permutation notation) ${\displaystyle V~~=~~\pi ^{-1}~F}$ or ${\displaystyle V(i)~~=~~i~\pi ^{-1}~F~~=~~F(\pi ^{-1}(i))}$

In ${\displaystyle \scriptstyle V}$ (as in ${\displaystyle \scriptstyle L}$) the last digit is always 0, and can be omitted. In ${\displaystyle \scriptstyle F}$ it is the first digit.
(When these vectors are permuted into each other, the omissible 0 from one does not necessarily become the omissible 0 in the other.)

The inversion number ( ) is the cardinality of the inversion set.
It is also the digit sum of the Lehmer code, the inversion vector and the factorial number.

### Knuth

In TAoCP Knuth defines an inversion as a pair of elements of the permutation that are out of order, rather than the pair of places:

If ${\displaystyle \scriptstyle i and ${\displaystyle \scriptstyle a_{i}>a_{j}}$, the pair ${\displaystyle \scriptstyle (a_{i},a_{j})}$ is called an inversion of the permutation; for example the permutation 3 1 4 2 has three inversions: (3, 1), (3, 2) and (4, 2).

According to the definition used in this article the inversions of 3 1 4 2 are (1, 2), (1, 4) and (3, 4).
The inversion set according to Knuth is the inversion set of the inverse permutation according to the definition used in this article (with the entries of the pairs exchanged).

His definition of the inversion table is the usual one though:

The inversion table ${\displaystyle \scriptstyle b_{1}b_{2}...b_{n}}$ of the permutation ${\displaystyle \scriptstyle a_{1}a_{2}...a_{n}}$ is obtained by letting ${\displaystyle \scriptstyle b_{j}}$ be the number of elements to the left of ${\displaystyle \scriptstyle j}$ that are greater than ${\displaystyle \scriptstyle j}$.

## Example: Permutations of six elements

The following images show two permutations inverse to each other.

Lehmer code and inversion vector are calculated with the help of the Rothe diagram on the left.

The little-endian factorial number is shown as the vector of row sums of the inversion set triangle.
${\displaystyle \scriptstyle F=\pi V}$ means ${\displaystyle \scriptstyle F(i)=i\pi V=V(\pi (i))}$ (compare Permutation notation), so ${\displaystyle \scriptstyle F}$ can also be seen in ${\displaystyle \scriptstyle V}$ below the Rothe diagram by using the blue inverse permutation on top as index.
E.g. in the first example ${\displaystyle \scriptstyle F(3)=V(\pi (3))=V(4)=1}$. Or graphically: To find ${\displaystyle \scriptstyle F(3)}$, go down from the blue 3 to find the red 1.

These permutations are at the positions 674 and 327 in the reverse colexicographic order of finite permutations (compare this list).

 Permutation 2 5 4 6 3 1 (Wolfram) (the inverse 6 1 5 3 2 4 is shown below) ${\displaystyle \scriptstyle F=\pi V}$ ${\displaystyle \scriptstyle F(3)=V(\pi (3))=V(4)=1}$ ${\displaystyle \scriptstyle V=\pi ^{-1}F}$ ${\displaystyle \scriptstyle V(3)=F(\pi ^{-1}(3))=F(5)=3}$ Permutation 6 1 5 3 2 4 (Wolfram) (the inverse 2 5 4 6 3 1 is shown above) ${\displaystyle \scriptstyle F=\pi V}$ ${\displaystyle \scriptstyle F(3)=V(\pi (3))=V(5)=1}$ ${\displaystyle \scriptstyle V=\pi ^{-1}F}$ ${\displaystyle \scriptstyle V(3)=F(\pi ^{-1}(3))=F(4)=2}$

Computation with Mathematica:

I: p1 = {2,5,4,6,3,1}
I: p2 = {6,1,5,3,2,4}

I: ToInversionVector[p1]
O: {5,0,3,1,0}
I: ToInversionVector[p2]
O: {1,3,2,2,1}

I: ToOrderedPairs[PermutationGraph[p1]]
O: {{2,1},{3,1},{4,1},{5,1},{6,1},{4,3},{5,3},{6,3},{5,4},{1,2},{1,3},{1,4},{1,5},{1,6},{3,4},{3,5},{3,6},{4,5}}
I: ToOrderedPairs[PermutationGraph[p2]]
O: {{6,1},{3,2},{5,2},{6,2},{5,3},{6,3},{5,4},{6,4},{6,5},{1,6},{2,3},{2,5},{2,6},{3,5},{3,6},{4,5},{4,6},{5,6}}