Inversion (discrete mathematics)

In computer science and discrete mathematics, an inversion in a sequence is a pair of elements that are out of their natural order.
Definitions.
Inversion.
Let formula_1 be a permutation. If formula_2 and formula_3, either the pair of places formula_4 or the pair of elements formula_5 is called an inversion of formula_1.
The inversion is usually defined for permutations, but may also be defined for sequences:<br>Let formula_7 be a sequence (or multiset permutation). If formula_2 and formula_9, either the pair of places formula_4 or the pair of elements formula_11 is called an inversion of formula_7.
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 set is the set of all inversions. A permutation's inversion set according to the place-based definition is that of the inverse permutation's inversion set according to the element-based definition, and vice versa, just with the elements of the pairs exchanged.
Inversion number.
The inversion number formula_13 of a sequence formula_14, is the cardinality of inversion set. It is a common measures of (pre-)sortedness of a permutation or sequence. This value is comprised between 0 and formula_15 included.
For example formula_16 since the sequence is ordered. Also formula_17 as each pairs formula_18 is an inversion. This last example shows that a sort that is intuitively sorted can still have a quadratic number of inversions.
It is the number of crossings in the arrow diagram of the permutation, its Kendall tau distance from the identity permutation, and the sum of each of the inversion related vectors defined below.
It does not matter if the place-based or the element-based definition of inversion is used to define the inversion number, because a permutation and its inverse have the same number of inversions.
Other measures of (pre-)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. Standard comparison sorting algorithms can be adapted to compute the inversion number in time .
Inversion related vectors.
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 .)
This article uses the term "inversion vector" (formula_19) like Wolfram. 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" (formula_20) and "right inversion count" (formula_21). Interpreted as a factorial number the left inversion count gives the permutations reverse colexicographic, and the right inversion count gives the lexicographic index.
Inversion vector formula_19:<br>With the "element-based" definition formula_23 is the number of inversions whose "smaller" (right) component is formula_24.
Left inversion count formula_20:<br>With the "place-based" definition formula_31 is the number of inversions whose "bigger" (right) component is formula_24.
Right inversion count formula_21, often called "Lehmer code":<br>With the "place-based" definition formula_39 is the number of inversions whose "smaller" (left) component is formula_24.
Both formula_19 and formula_21 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. formula_39 is the sum of inversions in row formula_24 of the Rothe diagram, while formula_23 is the sum of inversions in column formula_24. The permutation matrix of the inverse is the transpose, therefore formula_19 of a permutation is formula_21 of its inverse, and vice versa.
Example: All permutations of four elements.
The following sortable table shows the 24 permutations of four elements with their place-based inversion sets, inversion related vectors and inversion numbers. (The small columns are reflections of the columns next to them, and can be used to sort them in colexicographic order.)
It can be seen that formula_19 and formula_20 always have the same digits, and that formula_20 and formula_21 are both related to the place-based inversion set. The nontrivial elements of formula_20 are the sums of the descending diagonals of the shown triangle, and those of formula_21 are the sums of the ascending diagonals. (Pairs in descending diagonals have the right components 2, 3, 4 in common, while pairs in ascending diagonals have the left components 1, 2, 3 in common.)
The default order of the table is reverse colex order by formula_1, which is the same as colex order by formula_20. Lex order by formula_1 is the same as lex order by formula_21.
Weak order of permutations.
The set of permutations on "n" items can be given the structure of a partial order, called the weak order of permutations, which forms a lattice.
The Hasse diagram of the inversion sets ordered by the subset relation forms the skeleton of a permutohedron.
If a permutation is assigned to each inversion set using the place-based definition, the resulting order of permutations is that of the permutohedron, where an edge corresponds to the swapping of two elements with consecutive values. This is the weak order of permutations. The identity is its minimum, and the permutation formed by reversing the identity is its maximum.
If a permutation were assigned to each inversion set using the element-based definition, the resulting order of permutations would be that of a Cayley graph, where an edge corresponds to the swapping of two elements on consecutive places. This Cayley graph of the symmetric group is similar to its permutohedron, but with each permutation replaced by its inverse.
See also.
Sequences in the OEIS: