Inversion (discrete mathematics)

Let ${\displaystyle \pi }$ be a permutation. There is an inversion of ${\displaystyle \pi }$ between ${\displaystyle i}$ and ${\displaystyle j}$ if ${\displaystyle i<j}$ and ${\displaystyle \pi (i)>\pi (j)}$. The inversion is indicated by an ordered pair containing either the places ${\displaystyle (i,j)}$[1][2] or the elements ${\displaystyle {\bigl (}\pi (i),\pi (j){\bigr )}}$.[3][4][5]

The inversion set is the set of all inversions. A permutation's inversion set using place-based notation is the same as the inverse permutation's inversion set using element-based notation with the two components of each ordered pair exchanged. Likewise, a permutation's inversion set using element-based notation is the same as the inverse permutation's inversion set using place-based notation with the two components of each ordered pair exchanged.[6]

Inversions are usually defined for permutations, but may also be defined for sequences:
Let ${\displaystyle S}$ be a sequence (or multiset permutation[7]). If ${\displaystyle i<j}$ and ${\displaystyle S(i)>S(j)}$, either the pair of places ${\displaystyle (i,j)}$[7][8] or the pair of elements ${\displaystyle {\bigl (}S(i),S(j){\bigr )}}$[9] is called an inversion of ${\displaystyle S}$.

For sequences, inversions according to the element-based definition are not unique, because different pairs of places may have the same pair of values.

The inversion number ${\displaystyle {\mathtt {inv}}(X)}$[10] of a sequence ${\displaystyle X=\langle x_{1},\dots ,x_{n}\rangle }$, is the cardinality of the inversion set. It is a common measure of sortedness (sometimes called presortedness) of a permutation[5] or sequence.[9] The inversion number is between 0 and ${\displaystyle {\frac {n(n-1)}{2}}}$ inclusive. A permutation and its inverse have the same inversion number.

For example ${\displaystyle {\mathtt {inv}}(\langle 1,2,\dots ,n\rangle )=0}$ since the sequence is ordered. Also, when ${\displaystyle n=2m}$ is even, ${\displaystyle {\mathtt {inv}}(\langle m+1,m+2,\dots ,2m,1,2,\dots ,m\rangle )=m^{2}}$ (because each pair ${\displaystyle (1\leq i\leq m<j\leq 2m)}$ is an inversion). This last example shows that a set that is intuitively "nearly sorted" can still have a quadratic number of inversions.

The inversion number is the number of crossings in the arrow diagram of the permutation,[6] the permutation's Kendall tau distance from the identity permutation, and the sum of each of the inversion related vectors defined below.

Other measures of sortedness include the minimum number of elements that can be deleted from the sequence to yield a fully sorted sequence, the number and lengths of sorted "runs" within the sequence, the Spearman footrule (sum of distances of each element from its sorted position), and the smallest number of exchanges needed to sort the sequence.[11] Standard comparison sorting algorithms can be adapted to compute the inversion number in time O(n log n).[12]

Three similar vectors are in use that condense the inversions of a permutation into a vector that uniquely determines it. They are often called inversion vector or Lehmer code. (A list of sources is found here.)

This article uses the term inversion vector (${\displaystyle v}$) like Wolfram.[13] The remaining two vectors are sometimes called left and right inversion vector, but to avoid confusion with the inversion vector this article calls them left inversion count (${\displaystyle l}$) and right inversion count (${\displaystyle r}$). Interpreted as a factorial number the left inversion count gives the permutations reverse colexicographic,[14] and the right inversion count gives the lexicographic index.

Rothe diagram

Inversion vector ${\displaystyle v}$:
With the element-based definition ${\displaystyle v(i)}$ is the number of inversions whose smaller (right) component is ${\displaystyle i}$.[3]

${\displaystyle v(i)}$ is the number of elements in ${\displaystyle \pi }$ greater than ${\displaystyle i}$ before ${\displaystyle i}$.

${\displaystyle v(i)~~=~~\#\{k\mid k>i~\land ~\pi ^{-1}(k)<\pi ^{-1}(i)\}}$

Left inversion count ${\displaystyle l}$:
With the place-based definition ${\displaystyle l(i)}$ is the number of inversions whose bigger (right) component is ${\displaystyle i}$.

${\displaystyle l(i)}$ is the number of elements in ${\displaystyle \pi }$ greater than ${\displaystyle \pi (i)}$ before ${\displaystyle \pi (i)}$.

${\displaystyle l(i)~~=~~\#\left\{k\mid k<i~\land ~\pi (k)>\pi (i)\right\}}$

Right inversion count ${\displaystyle r}$, often called Lehmer code:
With the place-based definition ${\displaystyle r(i)}$ is the number of inversions whose smaller (left) component is ${\displaystyle i}$.

${\displaystyle r(i)}$ is the number of elements in ${\displaystyle \pi }$ smaller than ${\displaystyle \pi (i)}$ after ${\displaystyle \pi (i)}$.

${\displaystyle r(i)~~=~~\#\{k\mid k>i~\land ~\pi (k)<\pi (i)\}}$

Both ${\displaystyle v}$ and ${\displaystyle r}$ can be found with the help of a Rothe diagram, which is a permutation matrix with the 1s represented by dots, and an inversion (often represented by a cross) in every position that has a dot to the right and below it. ${\displaystyle r(i)}$ is the sum of inversions in row ${\displaystyle i}$ of the Rothe diagram, while ${\displaystyle v(i)}$ is the sum of inversions in column ${\displaystyle i}$. The permutation matrix of the inverse is the transpose, therefore ${\displaystyle v}$ of a permutation is ${\displaystyle r}$ of its inverse, and vice versa.