Inversion (discrete mathematics)

Inversion is a concept in discrete mathematics to measure how much a sequence is out of its natural order.

A permutation, its inversion set and its left inversion count

(An inversion of a permutation is not to be confused with the inverse of a permutation. Also not with point reflection.)



Definitions

edit
 
Map from the place-based to the element-based inversions of a permutation of four elements
 
The element-based inversion multiset of this sequence contains (2,1) twice.

A permutation   has an inversion for each pair of elements that are out of their natural order, i.e. when   but  .
It may be identified by the pair of places   or by the pair of elements  .
This article favours the former convention (although the latter seems to be more common).


The inversion set of a permutation is the set of all its inversions.
For an  -element permutation the number of potential elements is the triangular number  .

The element-based inversion set is essentially the place-based inversion set of the inverse permutation, just with the elements of the pairs exchanged.

For sequences the element-based inversion set has to be defined as a multiset, as many pairs of places can have the same pair of elements.


The permutation graph has the elements of the permutation as vertices and an edge between elements that are out of order,
i.e. an edge is an inversion according to the element-based definition:   is an edge iff  .
It is more common to write that   is an edge iff  . The latter is often written as  .

The permutation graphs of inverse permutations are isomorphic. That of   can be generated from that of   by changing each vertex   to  .

It seems that the permutation graph is only defined with place-based inversions. If it were generalized to apply to sequences, it would thus have to be defined as a multigraph.


The inversion number ( A034968 ) is the cardinality of the inversion set;
thus also the digit sum of the inversion related vectors;
and also the number of crossings in the arrow diagram of the permutation.


The parity of a permutation is the parity of its inversion number.
The sign of a permutation (the determinant of its matrix) corresponds to the parity: Even permutations have sign 1, odd permutations sign −1.


edit

There are four ways to condense the inversions of a permutation into a vector that uniquely determines it. Three of them are in use. (See sources below).

This article uses the terms left inversion count (l) and right inversion count (r) like Gnedin (similar to Calude and Deutsch), and the term inversion vector (v) like Wolfram.

The left and right inversion counts have the feature that interpreted as factorial numbers they determine the permutation's reverse colexicographic and lexicographic index.
The inversion vector does not appear to have a similar advantage, but it is widely used anyway.


Left inversion count l:
With the place-based definition   is the number of inversions whose bigger (right) component is  .

  is the number of elements in   greater than   before  .
 


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

  is the number of elements in   smaller than   after  .
 


Inversion vector v:
With the element-based definition   is the number of inversions whose smaller (right) component is  .

  is the number of elements in   greater than   before  .
 

A different way to say the same thing may be more intuitive:

  is the number of elements in   greater than   before  .
 

The latter definition would also work for a sequence, which does not have an inverse.


Relationship between l and v:

 
    (vector   permuted by   is  , compare Permutation notation)
 
   

The first digit of l and the last digit of v are always 0, and can be omitted.
When these vectors are permuted into each other, the omissible 0 from one does not necessarily become the omissible 0 in the other.


Relationship between r and v:
Both r and v can be found with the help of a Rothe diagram,
which is a permutation matrix with the 1s represented by dots, and an inversion in every position that has a dot to the right and below it.
  is the sum of inversions in row   of the Rothe diagram, while   is the sum of inversions in column  .
The permutation matrix of the inverse is the transpose. Therefore v of a permutation is r of its inverse, and vice versa.


Relationship between r and l:

 

This is proven in Gnedin & Olshanski 2012, and mentioned as R[i]+i=p[i]+L[i] in  A138159.


Permutations that are equal up to fixed points can be seen as equal. Equivalently, inversion related vectors that are equal up to trailing 0s can be seen as equal.
While for r and v the omissible 0 on the right is part of the trailing 0s, for l the omissible 0 on the left is separate from them.

Example: Permutations of six elements

edit

The following images show two inverse permutations, their 9 inversions and the corresponding vectors.

 
 
 
 
 
 
 

 
Permutation matrix
 
Rothe diagram
 
Place-based inversion set

l = (0, 0, 1, 0, 3, 5)
rev colex rank: 530100! = 674
r = (1, 3, 2, 2, 1, 0)
lex rank: 132210! = 209

 
Element-based inversion set

 
Permutation graph
 
 
 
 
 
 
 

 
Permutation matrix
 
Rothe diagram
 
Place-based inversion set

l = (0, 1, 1, 2, 3, 2)
rev colex rank: 232110! = 327
r = (5, 0, 3, 1, 0, 0)
lex rank: 503100! = 620

 
Element-based inversion set

 
Permutation graph



Mathematica omits the 0 at the end of the inversion vector. Compare p1 and p2 in Wolfram Alpha.

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}}

Example: All permutations of four elements

edit
 
The six possible inversions of a 4-element permutation

The following sortable table shows the 24 permutations of four elements with their place-based inversion sets, inversion related vectors and inversion numbers.

It is shown twice, so different orders can be compared to each other. (The Python script used to create it is shown here.)

The columns with small text are the reflections of the main columns. Sorting by them gives the colexicographic order of the corresponding main column.


Inversion vector v and left inversion count l are shown next to each other, because they have the same digits.

Left and right inversion counts are related to the place-based inversion sets shown between them:
The nontrivial elements of l are the sums of the descending diagonals of the triangle, and those of r are the sums of the of the ascending diagonals.


The default order of the table is the reverse colex order by  , which is the same as the colex order by l. (This header cell is highlighted by a darker gray.)

Lex order by   is the same as lex order by r.


Ordering one table by r and the other one by v brings inverse permutations next to each other, i.e. those whose matrices are reflected at the main diagonal.

Ordering one table by reflected l and the other one by v brings permutations next to each other whose permutation matrices are reflected at the antidiagonal.

Ordering one table by reflected l and the other one by r brings permutations next to each other whose permutation matrices are rotated by 180°.
(It can be seen, that these permutations' inversion sets are symmetric to each other, which corresponds to l and r being symmetric to each other.)


Note that the set of all r, the set of all v and the set of all reflected l for the same symmetric group are equal.
So sorting by two columns that have the omissible 0 at the same end makes these columns equal.

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
π v l p-b r #
0   1234 4321 0000 0000 0000 0000   0000 0000 0
1   2134 4312 1000 0001 0010 0100   1000 0001 1
2   1324 4231 0100 0010 0100 0010   0100 0010 1
3   3124 4213 1100 0011 0110 0110   2000 0002 2
4   2314 4132 2000 0002 0200 0020   1100 0011 2
5   3214 4123 2100 0012 0210 0120   2100 0012 3
6   1243 3421 0010 0100 1000 0001   0010 0100 1
7   2143 3412 1010 0101 1010 0101   1010 0101 2
8   1423 3241 0110 0110 1100 0011   0200 0020 2
9   4123 3214 1110 0111 1110 0111   3000 0003 3
10   2413 3142 2010 0102 1200 0021   1200 0021 3
11   4213 3124 2110 0112 1210 0121   3100 0013 4
12   1342 2431 0200 0020 2000 0002   0110 0110 2
13   3142 2413 1200 0021 2010 0102   2010 0102 3
14   1432 2341 0210 0120 2100 0012   0210 0120 3
15   4132 2314 1210 0121 2110 0112   3010 0103 4
16   3412 2143 2200 0022 2200 0022   2200 0022 4
17   4312 2134 2210 0122 2210 0122   3200 0023 5
18   2341 1432 3000 0003 3000 0003   1110 0111 3
19   3241 1423 3100 0013 3010 0103   2110 0112 4
20   2431 1342 3010 0103 3100 0013   1210 0121 4
21   4231 1324 3110 0113 3110 0113   3110 0113 5
22   3421 1243 3200 0023 3200 0023   2210 0122 5
23   4321 1234 3210 0123 3210 0123   3210 0123 6
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
π v l p-b r #
0   1234 4321 0000 0000 0000 0000   0000 0000 0
1   2134 4312 1000 0001 0010 0100   1000 0001 1
2   1324 4231 0100 0010 0100 0010   0100 0010 1
3   3124 4213 1100 0011 0110 0110   2000 0002 2
4   2314 4132 2000 0002 0200 0020   1100 0011 2
5   3214 4123 2100 0012 0210 0120   2100 0012 3
6   1243 3421 0010 0100 1000 0001   0010 0100 1
7   2143 3412 1010 0101 1010 0101   1010 0101 2
8   1423 3241 0110 0110 1100 0011   0200 0020 2
9   4123 3214 1110 0111 1110 0111   3000 0003 3
10   2413 3142 2010 0102 1200 0021   1200 0021 3
11   4213 3124 2110 0112 1210 0121   3100 0013 4
12   1342 2431 0200 0020 2000 0002   0110 0110 2
13   3142 2413 1200 0021 2010 0102   2010 0102 3
14   1432 2341 0210 0120 2100 0012   0210 0120 3
15   4132 2314 1210 0121 2110 0112   3010 0103 4
16   3412 2143 2200 0022 2200 0022   2200 0022 4
17   4312 2134 2210 0122 2210 0122   3200 0023 5
18   2341 1432 3000 0003 3000 0003   1110 0111 3
19   3241 1423 3100 0013 3010 0103   2110 0112 4
20   2431 1342 3010 0103 3100 0013   1210 0121 4
21   4231 1324 3110 0113 3110 0113   3110 0113 5
22   3421 1243 3200 0023 3200 0023   2210 0122 5
23   4321 1234 3210 0123 3210 0123   3210 0123 6

(A more detailled version of this table, including element-based inversion sets and the unused fourth vector, can be found here.)

Weak order of permutations

edit

The Hasse diagram below in the middle shows the 24 inversion sets ordered by the subset relation.

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   is an edge iff  , i.e. when only two elements with consecutive values are swapped.
(In the central diagram it can be seen on which positions the swapped elements are, by looking which digit changes for the edge.)

The bitwise   ordering of the left and right inversion counts of these permutations gives the same order (because both are diagonal sums of the inversion set triangles).

 
Permutations and left inversion counts l
 
Inversion sets (place-based)
 
Permutations and right inversion counts r


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   is an edge iff  , i.e. when only two elements on consecutive places are swapped.

This Cayley graph of the symmetric group is similar to its permutohedron, but with each permutation replaced by its inverse.

For sequences inversion sets and the related vectors are not unique. Their place-based inversion sets are multisets, and their inversion vectors can have bigger digits than would be allowed in a factorial number.

0
1
2
3
4
5
S # l p-b r u e-b v
5

 
 
 
 

0011 1100 0 0000 0000 . .. ...   ... .. . 0000 0000 0000 0000 . .. ... ... .. . 0000 0000
17

 
 
 
 

0101 1010 1 0100 0010 . .1 ...   ... 1. . 0100 0010 0010 0100 1 .. ... ... .. 1 1000 0001
20

 
 
 
 

0110 0110 2 2000 0002 . .. .11   11. .. . 0110 0110 0020 0200 2 .. ... ... .. 2 2000 0002
65

 
 
 
 

1001 1001 2 0110 0110 1 1. ...   ... .1 1 2000 0002 0020 0200 2 .. ... ... .. 2 2000 0002
68

 
 
 
 

1010 0101 3 2010 0102 1 .. 1.1   1.1 .. 1 2010 0102 0030 0300 3 .. ... ... .. 3 3000 0003
80

 
 
 
 

1100 0011 4 2200 0022 . 11 11.   .11 11 . 2200 0022 0040 0400 4 .. ... ... .. 4 4000 0004
 

Similar permutations have similar inversion sets and corresponding vectors.

Some can be ordered in arrays, like the one on the right, corresponding to the number triangle  A211367.

wp(4,8,1,2) = (0,4,8,12, 1,5,9,13, 2,6,10,14, 3,7,11,15)

r = v = (0,3,6,9, 0,2,4,6, 0,1,2,3, 0,0,0,0)
l = (0,0,0,0, 3,2,1,0, 6,4,2,0, 9,6,3,0)
wp(14,13,11,7) = (0,14,13,3, 11,5,6,8, 7,9,10,4, 12,2,1,15)

r = v = (0,13,12,2, 9,3,3,4, 3,3,3,2, 2,1,0,0)
l = (0,0,1,2, 2,3,3,3, 4,3,3,9, 2,12,13,0)
wp(13,11, 7,15) = (0,15,14,1, 13,2,3,12, 11,4,5,10, 6,9,8,7)

r = (0,14,13,0, 11,0,0,8, 7,0,0,4, 0,2,1,0)
v = (0,2,3,3, 5,5,6,8, 7,6,5,4, 3,2,1,0)
l = (0,0,1,2, 2,3,3,3, 4,5,5,5, 6,6,7,8)

Sources

edit

Books

edit

Cramer 1750

edit

Cramer defines the inversion under the name dérangement to calculate the sign of a permutation.

For the permutation 3 1 2 the dérangements are given as 3 before 1 and 3 before 2.

Cramer, Gabriel: Introduction à l'analyse des lignes courbes algébriques. Genève : chez les Frères Cramer & Cl. Philibert 1750 — Appendice (p. 658)

Chabert (1999). A history of algorithms : from the pebble to the microchip. Berlin New York: Springer. ISBN 9783540633693.  — 9.1 Cramers rule (p. 286)

Rothe 1800

edit

Rothe essentially defines the right inversion count r under the name Stellenexponenten — but with each place bigger by 1.

  is the position of   among the   with   in numerical order. (p. 163)

Strangely he counts from 1 rather than 0, which later leads to avoidable additions and subtractions by 1:

  (p. 165)
Each permutation has sign   when the sum of the   is even, and sign   when it is odd. (p. 266)

For the permutation   the Stellenexponenten are given as  .

Muir translates Stellenexponent as place-index and calls it “an ill-advised and purposeless modification of Cramers idea of a ‘derangement’”. (The Theory of the Determinant..., p. 55)

"Ueber Permutationen, in Beziehung auf die Stellen ihrer Elemente. Anwendung der daraus abgeleiteten Satze auf das Eliminationsproblem". In Hindenburg, Carl, ed., Sammlung Combinatorisch-Analytischer Abhandlungen, pp. 263–305, Bey G. Fleischer dem jüngern, 1800.

Laisant 1888

edit

After defining the factorial number system Laisant defines the right inversion count r under the name signe figuratif.

For the permutation   the signe figuratif is given as  .

Laisant, Charles-Ange (1888), "Sur la numération factorielle, application aux permutations", Bulletin de la Société Mathématique de France (in French), 16: 176–183


Aigner 2007

edit
p-b perm

Now we look at permutations of   in word form  .
The pair   is called an inversion if   but  .

A moment's thought shows that   is an inversion if and only if the edges   and   cross in the diagram.
Hence the inversion number   equals the number of crossings.

Aigner, Martin (2007). A course in enumeration. Berlin New York: Springer. ISBN 3642072534. Word Representation (p. 27 ff)


Comtet 1974

edit
p-b perm

An inversion of a permutation   is a pair   such that   and  . In this case we say that   has an inversion in  .

He uses the same definition for a non-bijective map in exercise 21 on permutations (p. 266).

Comtet, Louis (1974). Advanced combinatorics; the art of finite and infinite expansions. Dordrecht,Boston: D. Reidel Pub. Co. ISBN 9027704414.  — 6.4 Inversions of a permutation of [n] (p. 237)


Cormen et al. 2001

edit
p-b seq

Let   be an array of n distinct numbers. If   and  , then the pair   is called an inversion of  .

Cormen, Thomas (2001). Introduction to algorithms. Cambridge, Mass: MIT Press. ISBN 0262531968.  — 2-4 Inversions (p. 41) and 5.2-5 (p. 122)


Knuth 1973

edit
e-b perm
v as inversion table

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).

The inversion table   of the permutation   is obtained by letting   be the number of elements to the left of   that are greater than  .
In other words,   is the number of inversions whose second component is  .

Knuth, Donald (1973). The art of computer programming. Reading, Mass: Addison-Wesley Pub. Co. ISBN 0201896850.  — 5.1.1 Inversions (p. 11)


Pemmaraju & Skiena 2003

edit
e-b perm
v as inversion vector

A pair of elements   in a permutation   represents an inversion if   and  .
An inversion is a pair of elements that are out of order [...]

For any  -permutation  , we can define an inversion vector   as follows. For each integer  ,  , the  th element of   is the number of elements in   greater than   to the left of  .

Pemmaraju, Sriram (2003). Computational discrete mathematics : combinatorics and graph theory with Mathematica. Cambridge, U.K. New York: Cambridge University Press. ISBN 9780521806862.  — 2.2 Inversions and Inversion Vectors (p. 69)


Vitter & Flajolet 1990

edit
e-b perm
v as inversion table

An inversion in permutation   is an “out of order” pair   of elements, in which   but  .
The number of inversions is thus a measure of the amount of disorder in a permutation.

The inversion table of the permutation   is the ordered sequence

 , where  .

Leeuwen, J (1990). Handbook of theoretical computer science. Amsterdam New York Cambridge, Mass: Elsevier MIT Press. ISBN 9780444880710.  — 3.1 Inversions (p. 459)


Grätzer 2016

edit
e-b perm

The authors define the usual strict linear ordering   on   as  .

Let   be a permutation on  . An inversion of   is an ordered pair   satisfying  .
The inversion set of   is then defined as  .

The inversion set of   is given as  .

In the footnote it is mentioned that other authors often use the definition as an ordered pair   such that  .
TAoCP is given as an example — despite the fact that Knuth uses essentially the same definition (see above).

Gratzer, George (2016). Lattice theory. special topics and applications. Cham, Switzerland: Birkhäuser. ISBN 331944235X.  — 7-2 Basic objects (p. 221)


Joshi 1989

edit
e-b seq
r as inversion table or inversion vector

Let   be a sequence of real numbers.
By an inversion in  , we mean a pair   such that   but  .
For each  , let   = the number of inversions whose first entry is  , i.e.

 .

Then the sequence   is called the inversion table or inversion vector of  . [...]
The permutation   has   as its inversion table.

Joshi, K. D. (1989). Foundations of discrete mathematics. New York New Delhi, India: Wiley Wiley Eastern Ltd. ISBN 8122401201.  — Definition 3.12 (p. 188)


Bóna 2012

edit
e-b perm

Bóna first uses the definition with elements:

Let   be a permutation. We say that   is an inversion of   if   but  .
Permutation 31524 has four inversions, namely (3, 1), (3, 2), (5, 2), and (5,4).

2.1 Inversions (p. 43)

p-b seq

But for multisets he uses places instead:

An inversion of a permutation   of a multiset is defined just as it was for permutations of sets, that is,   is a inversion if  , but  ·
The multiset-permutation 1322 has two inversions, (2, 3), and (2, 4).

2.2 Inversions in Permutations of Multisets (p. 57)

The definition of non-inversions also uses places:

[...] look at all non-inversions of a generic permutation  ; that is, pairs so that   and  .

4.4.1.1 An exponential upper bound (p. 141)

Bóna, Miklós (2012). Combinatorics of permutations. Boca Raton, FL: CRC Press. ISBN 1439850518. 


Calude et al. 2003

edit
l as left-inversion vector
r as right-inversion vector

For permutations, an inversion vector is used as an auxiliary array because it fills in the holes made by the elements of the prefix in its defining sequence.
For the permutation   the right-inversion vector   is defined by the rule that   is the number of   to the right of but smaller than  ;
in the left-inversion vector,   is the number of   to the left of but larger than  .

Calude, Cristian (2003). Discrete mathematics and theoretical computer science : 4th international conference, DMTCS 2003, Dijon, France, July 7-12, 2003 : proceedings. Berlin New York: Springer. ISBN 3540405054. Generating Gray codes... (p. 81)


Lothaire 2002

edit
p-b perm
l as Lehmer encoding

If   is [a permutation of  ] an inversion of   is a pair   such that   and  .

11.1. Prelimiaries (p. 367)

Let   be a permutation of  . For  , let   be the number of indices   such that  . The word   will be called the Lehmer encoding of  .

To the permutation   corresponds the Lehmer encoding  .

11.4. Inversions of permutations with a given shape (p. 372)

Lothaire, M (2002). Algebraic combinatorics on words. Cambridge New York: Cambridge University Press. ISBN 0521812208. 

Papers

edit

Vajnovszki 2011

edit
p-b perm
l as Lehmer code

The pair   is an inversion of   if   but  . [...]

An integer sequence   is said to be subexcedent if   for  , and the set of lenth-  subexcedent sequences is denoted by   [...].
The Lehmer code [5] is a bijection code :   which maps each permutation   to a subexcedent sequence  
where, for all  ,   is the number of inversions   in   (or equivalently, the number of entries in   larger than   and on its left).
[5]      D. H. Lehmer, Teaching combinatorial tricks to a computer, in Proc. Sympos. Appl. Math., 10 (1960), Amer. Math. Soc., 179-193.

Vajnovszki. A new Euler–Mahonian constructive bijection — pp. 1-2


Gnedin & Olshanski 2012

edit
p-b perm
l as left inversion count
r as right inversion count

For  , a pair of positions   is an inversion in   if   and  .
If   is an inversion, we say that it is a left inversion for  , and a right inversion for  .
Introduce the counts of left and right inversions,

 ,

respectively (of course, for the general   these quantities may be infinite).

4. A construction from independent geometric variables (p. 624)

The authors proof the following formula for balanced permutations, which include finite permutations:

 

Lemma 4.6 (p. 627)

Gnedin; Olshanski. The two-sided infinite extension of the Mallows model for random permutations


Deutsch et al. 2008

edit
p-b perm
r as right inversion vector

In a permutation  , an inversion is a pair   such that  . [...]
If   is the number of   with  , then   is called the right inversion vector of   [...].

Deutsch; Pergola; Pinzani. Six bijections between deco polyominoes and permutations — p. 5


Barth & Mutzel 2004

edit
e-b seq
 
Crossings in a bilayer graph...
 
...correspond to inversions of a non-bijective map.

In a sequence   of pairwise comparable elements  , a pair   is called an inversion if   and  .

A crucial point of the article is illustrated by the images on the right: A bilayer graph that does not describe a map corresponds to a map that has the edges (green) as its domain and one layer of the vertices (blue) as its codomain. The number of crossings in the bilayer graph can be calculated as the number of inversions of the map.
In this example the map is  .

 ,   and  , so with the place-based definition the sequence would have the inversions   and  .
With the element-based definition, chosen by the authors, one could say that the sequence has the inversion   twice.

Barth, Wilhelm; Mutzel, Petra (2004). "Simple and Efficient Bilayer Cross Counting". Journal of Graph Algorithms and Applications 8 (2): 179–194. doi:10.7155/jgaa.00088.  — 2 Bilayer Cross Counts and Inversion Numbers (p. 183)