Inversion (discrete mathematics)
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.
Contents
Definitions[edit]
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 in the matrix is . 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 () is the vector of the row sums of the Rothe diagram. It is the inversion vector of the inverse permutation.
 is the number of elements in smaller than after . (In other words, is the number of inversions whose left component is .)
The inversion vector () or inversion table is the vector of the column sums of the Rothe diagram. It is the Lehmer code of the inverse permutation.
 is the number of elements in greater than before .
The littleendian factorial number () consists of the same numbers as the inversion vector, but in a different order.
 is the number of elements in greater than before . (In other words, is the number of inversions whose right component is .)
There is some terminology confusion, due to which in my material the littleendian factorial numbers are often called inversion vectors. This is going to be changed.
The relationship between and is:

or  (compare Permutation notation)  

or 
In (as in ) the last digit is always 0, and can be omitted. In 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 ( A034968 ) 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[edit]
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 and , the pair 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 of the permutation is obtained by letting be the number of elements to the left of that are greater than .
Example: Permutations of six elements[edit]
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 littleendian factorial number is shown as the vector of row sums of the inversion set triangle.
means (compare Permutation notation), so can also be seen in below the Rothe diagram by using the blue inverse permutation on top as index.
E.g. in the first example . Or graphically: To find , 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) 

Permutation 6 1 5 3 2 4 (Wolfram) 

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}}
Weak order of permutations[edit]

 See also: Symmetric group S_{4}
Arrays of permutations[edit]
The littleendian factorial numbers are erroneously called inversion vectors in these graphics.