Inversion (discrete mathematics)

From Wikiversity
Jump to: navigation, search
Created by Watchduck
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[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 little-endian 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 little-endian 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 (Sloane'sA034968 ) 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 little-endian 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)
(the inverse 6 1 5 3 2 4 is shown below)



Inversion example; formula 1 L.svg
Inversion example; Rothe diagram 1.svg
Inversion example; formula 1 V.svg
Inversion example; formula 1 F.svg

Permutation 6 1 5 3 2 4 (Wolfram)
(the inverse 2 5 4 6 3 1 is shown above)



Inversion example; formula 2 L.svg
Inversion example; Rothe diagram 2.svg
Inversion example; formula 2 V.svg
Inversion example; formula 2 F.svg

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 S4
Permutohedron of S4 with the permutations on top and the little-endian factorial numbers below
Permutohedron of S4 with inversion sets


Arrays of permutations[edit]

The little-endian factorial numbers are erroneously called inversion vectors in these graphics.

Sloane'sA211365      Loupe light.svg
Sloane'sA211366      Loupe light.svg
Chains of transpositions      Sloane'sA211367      Loupe light.svg
Rows of transpositions      Sloane'sA211368      Loupe light.svg
Transpositions      Sloane'sA211369      Loupe light.svg      (m,n) here corresponds to (n,m) in the array of 2-subsets.
Nested transpositions      Sloane'sA100630      Loupe light.svg
Circular shift to the right      Sloane'sA211370      Loupe light.svg
Circular shift to the left      Sloane'sA051683      Loupe light.svg


Rdrdo.svg Walsh permutations[edit]

wp( 3, 5, 9, 1)
wp( 4, 8, 1, 2)
wp(14,13,11, 7)