View source for Inversion (discrete mathematics)

[[File:Inversion set and vector of a permutation.svg|thumb|300px|A permutation, its inversion set and its left inversion count]]

[[w:Inversion (discrete mathematics)|Inversion]] is a concept in discrete mathematics to measure how much a sequence is out of its natural order.<br>

<small>(An inversion of a permutation is not to be confused with the [[w:Inverse function|inverse]] of a permutation. Also not with [[w:Point reflection|point reflection]].)</small>


__TOC__


==Definitions==
[[File:4-el perm invmap 11.svg|thumb|200px|Map from the place-based to the element-based inversions of a permutation of four elements]]
[[File:4-el sequence invmap 2101.svg|thumb|200px|The element-based inversion multiset of this sequence contains (2,1) twice.]]
A permutation <math>\pi</math> has an '''inversion''' for each pair of elements that are out of their natural order, i.e. when <math>i < j</math> but <math>\pi(i) > \pi(j)</math>.<br>
It may be identified by the pair of places <math>(i, j)</math> or by the pair of elements <math>\bigl(\pi(i), \pi(j)\bigr)</math>.<br>
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.<br>
For an <math>n</math>-element permutation the number of potential elements is the [[w:triangular number|triangular number]] <math>\scriptstyle { n \choose 2}</math>.

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

<small>For sequences the element-based inversion set has to be defined as a [[w:multiset|multiset]], as many pairs of places can have the same pair of elements.</small>


The '''[[w:Permutation graph|permutation graph]]''' has the elements of the permutation as vertices and an edge between elements that are out of order,<br>
i.e. an edge is an inversion according to the element-based definition: <math>\{\pi(i), \pi(j)\}</math> is an edge iff <math>i < j ~~ \land ~~ \pi(i) > \pi(j)</math>.<br>
It is more common to write that <math>\{i, j\}</math> is an edge iff <math>i < j ~~ \land ~~ \pi^{-1}(i) > \pi^{-1}(j)</math>. The latter is often written as <math>(i - j) \cdot \bigl(\pi^{-1}(i) - \pi^{-1}(j)\bigr) < 0</math>.

The permutation graphs of inverse permutations are [[w:Graph isomorphism|isomorphic]]. That of <math>\pi^{-1}</math> can be generated from that of <math>\pi</math> by changing each vertex <math>i</math> to <math>\pi(i)</math>.<br>

<small>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 [[w:multigraph|multigraph]].</small>


The '''inversion number''' ({{oeis|A034968 }}) is the cardinality of the inversion set;<br>
thus also the digit sum of the inversion related vectors;<br>
and also the number of crossings in the arrow diagram of the permutation.


The '''[[w:Parity of a permutation|parity]]''' of a permutation is the parity of its inversion number.<br>
The '''sign''' of a permutation (the [[w:Determinant|determinant]] of its matrix) corresponds to the parity: Even permutations have sign 1, odd permutations sign −1.


===Inversion related vectors===

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|sources]] below).

This article uses the terms ''left inversion count'' ({{invvect|l}}) and ''right inversion count'' ({{invvect|r}}) like [[#Gnedin & Olshanski 2012|Gnedin]] (similar to [[#Calude et al. 2003|Calude]] and [[#Deutsch et al. 2008|Deutsch]]), and the term [http://mathworld.wolfram.com/InversionVector.html ''inversion vector''] ({{invvect|v}}) like Wolfram.

The left and right inversion counts have the feature that interpreted as [[w:factorial number system|factorial numbers]] they determine the permutation's [[Lexicographic_and_colexicographic_order#Permutations|reverse colexicographic]] and lexicographic index.<br>
The inversion vector does not appear to have a similar advantage, but it is widely used anyway.


'''Left inversion count {{invvect|l}}:'''<br>
With the ''place-based'' definition <math>l(i)</math> is the number of inversions whose ''bigger'' (right) component is <math>i</math>.
:<math>l(i)</math> is the number of elements in <math>\pi</math> greater than <math>\pi(i)</math> before <math>\pi(i)</math>.
:<math>l(i) ~~=~~ \# \left\{ k \mid k < i ~\land~ \pi(k) > \pi(i) \right\}</math>


'''Right inversion count {{invvect|r}}, often called {{w|Lehmer code}}:'''<br>
With the ''place-based'' definition <math>r(i)</math> is the number of inversions whose ''smaller'' (left) component is <math>i</math>.
:<math>r(i)</math> is the number of elements in <math>\pi</math> smaller than <math>\pi(i)</math> after <math>\pi(i)</math>.
:<math>r(i) ~~=~~ \# \{ k \mid k > i ~\land~ \pi(k) < \pi(i) \}</math>


'''Inversion vector {{invvect|v}}:'''<br>
With the ''element-based'' definition <math>v(i)</math> is the number of inversions whose ''smaller'' (right) component is <math>i</math>.
:<math>v(i)</math> is the number of elements in <math>\pi</math> greater than <math>i</math> before <math>i</math>.
:<math>v(i) ~~=~~ \# \{ k \mid k > i ~\land~ \pi^{-1}(k) < \pi^{-1}(i) \}</math>
A different way to say the same thing may be more intuitive:
:<math>v\bigl(\pi(i)\bigr)</math> is the number of elements in <math>\pi</math> greater than <math>\pi(i)</math> before <math>\pi(i)</math>.
:<math>v\bigl(\pi(i)\bigr) ~~=~~ \# \{ k \mid k < i ~\land~ \pi(k) > \pi(i) \} ~~~~~~~~~~~~~~~~=~~ l(i)</math>
<small>The latter definition would also work for a sequence, which does not have an inverse.</small>

{| class="collapsible collapsed" style="width: 100%; border: 1px solid #aaa;"
!colspan="3" bgcolor="#f2f2f2"| Python functions
|- style="vertical-align: bottom;"
|
<syntaxhighlight lang="Python">
def left_inversion_count(p):
    n = len(p)
    v = [0] * n
    for i in range(n):
        count = 0
        for k in range(i):
            if p[k] > p[i]:
                count += 1
        v[i] = count
    return v
</syntaxhighlight>
|
<syntaxhighlight lang="Python">
def right_inversion_count(p):
    n = len(p)
    v = [0] * n
    for i in range(n):
        count = 0
        for k in range(i, n):
            if p[k] < p[i]:
                count += 1
        v[i] = count
    return v
</syntaxhighlight>
|
<syntaxhighlight lang="Python">
def inversion_vector(p_raw):
    if min(p_raw) == 1:  # assuming 1-based permutation
        p = [entry-1 for entry in p_raw]
    else:  # assuming 0-based permutation
        p = p_raw
    n = len(p)
    v = [0] * n
    for i in range(n):
        count = 0
        for k in range(i):
            if p[k] > p[i]:
                count += 1
        v[p[i]] = count
    return v
</syntaxhighlight>
|}


'''Relationship between {{invvect|l}} and {{invvect|v}}:'''
{|
|
:<math>v ~~=~~ l.\pi ~~=~~ l(\pi^{-1})</math>
|style="padding:0 50px"| <math>\Leftrightarrow</math>
| <math>v(i) ~~=~~ l\bigl(\pi^{-1}(i)\bigr)</math>
|style="padding-left:50px"| (vector <math>x</math> permuted by <math>\alpha</math> is <math>x.\alpha = x(\alpha^{-1})</math>, compare [[Permutation notation#Active right|Permutation notation]])
|-
|
:<math>l ~~=~~ v.\pi^{-1} ~~=~~ v(\pi)</math>
|style="padding:0 50px"| <math>\Leftrightarrow</math>
|<math>l(i) ~~=~~ v\bigl(\pi(i)\bigr)</math>
|
|}

The first digit of {{invvect|l}} and the last digit of {{invvect|v}} are always 0, and can be omitted.<br>
<small>When these vectors are permuted into each other, the omissible 0 from one does not necessarily become the omissible 0 in the other.</small>


'''Relationship between {{invvect|r}} and {{invvect|v}}:'''<br>
Both {{invvect|r}} and {{invvect|v}} can be found with the help of a '''Rothe diagram''',<br>
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.<br>
<math>r(i)</math> is the sum of inversions in row <math>i</math> of the Rothe diagram, while <math>v(i)</math> is the sum of inversions in column <math>i</math>.<br>
The permutation matrix of the inverse is the transpose. Therefore {{invvect|v}} of a permutation is {{invvect|r}} of its inverse, and vice versa.


'''Relationship between {{invvect|r}} and {{invvect|l}}:'''<br>
:<math>\pi(i) ~~=~~ i + r(i) - l(i)</math>
This is proven in [[#Gnedin & Olshanski 2012|Gnedin & Olshanski 2012]], and mentioned as <code>R[i]+i=p[i]+L[i]</code> in {{oeis|A138159}}.


Permutations that are equal up to [[w:Cycles and fixed points|fixed points]] can be seen as equal. Equivalently, inversion related vectors that are equal up to trailing 0s can be seen as equal.<br>
<small>While for {{invvect|r}} and {{invvect|v}} the omissible 0 on the right is part of the trailing 0s, for {{invvect|l}} the omissible 0 on the left is separate from them.</small>

==Example: Permutations of six elements==

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

{| class="wikitable" style="width: 100%;"
|
[[File:Inversion example; VF 1b.svg|thumb|220px|center|<math>v = l.\pi = l(\pi^{-1})</math><br><math>v(3) = l(\pi^{-1}(3)) = l(5) = 3</math>]]
[[File:Inversion example; VF 1a.svg|thumb|220px|center|<math>l = v.\pi^{-1} = v(\pi)</math><br><math>l(3) = v(\pi(3)) = v(4) = 1</math>]]
| <math>\begin{align}\pi & = \mathit{674} \\ & = (1~2~5~3~4~6) \\ & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 4 & 6 & 3 & 1 \end{pmatrix}\end{align}</math><br><br>[[File:Inversion example; permutation matrix 1.svg|thumb|center|220px|Permutation matrix]]
| [[File:Inversion example; Rothe 1.svg|center|350px|thumb|Rothe diagram]]
|style="vertical-align:top;"| [[File:Inversion example; invset p-b 1.svg|thumb|center|266px|Place-based inversion set]]<br>
<span style="font-size: 90%">
{{invvect|l}} = (<span style="opacity: .3;">0, </span>0, 1, 0, 3, 5)<br>
rev colex rank: 53010<span style="opacity: .3;">0</span><sub>!</sub> = 674<br>
{{invvect|r}} = (1, 3, 2, 2, 1<span style="opacity: .3;">, 0</span>)<br>
lex rank: 13221<span style="opacity: .3;">0</span><sub>!</sub> = 209<br>
</span>
|style="vertical-align:top;"| [[File:Inversion example; invset e-b 1.svg|thumb|center|200px|Element-based inversion set]]<br>[[File:Inversion example; graph 1.svg|thumb|center|200px|Permutation graph]]
|}

{| class="wikitable collapsible collapsed" style="width: 100%; text-align: center;"
!colspan="3"| Formulas
|-
| [[File:Inversion example; formula 1 l.svg|400px]]
| [[File:Inversion example; formula 1 r.svg|400px]]
| [[File:Inversion example; formula 1 v.svg|400px]]
|-
| [[File:Inversion example; formula 2 l.svg|400px]]
| [[File:Inversion example; formula 2 r.svg|400px]]
| [[File:Inversion example; formula 2 v.svg|400px]]
|}

{| class="wikitable" style="width: 100%;"
|
[[File:Inversion example; VF 2b.svg|thumb|220px|center|<math>v = l.\pi = l(\pi^{-1})</math><br><math>v(3) = l(\pi^{-1}(3)) = l(4) = 2</math>]]
[[File:Inversion example; VF 2a.svg|thumb|220px|center|<math>l = v.\pi^{-1} = v(\pi)</math><br><math>l(3) = v(\pi(3)) = v(5) = 1</math>]]
| <math>\begin{align}\pi & = \mathit{327} \\ & = (1~6~4~3~5~2) \\ & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 1 & 5 & 3 & 2 & 4 \end{pmatrix}\end{align}</math><br><br>[[File:Inversion example; permutation matrix 2.svg|thumb|center|220px|Permutation matrix]]
| [[File:Inversion example; Rothe 2.svg|center|350px|thumb|Rothe diagram]]
|style="vertical-align:top;"| [[File:Inversion example; invset p-b 2.svg|thumb|center|266px|Place-based inversion set]]<br>
<span style="font-size: 90%">
{{invvect|l}} = (<span style="opacity: .3;">0, </span>1, 1, 2, 3, 2)<br>
rev colex rank: 23211<span style="opacity: .3;">0</span><sub>!</sub> = 327<br>
{{invvect|r}} = (5, 0, 3, 1, 0<span style="opacity: .3;">, 0</span>)<br>
lex rank: 50310<span style="opacity: .3;">0</span><sub>!</sub> = 620<br>
</span>
|style="vertical-align:top;"| [[File:Inversion example; invset e-b 2.svg|thumb|center|200px|Element-based inversion set]]<br>[[File:Inversion example; graph 2.svg|thumb|center|200px|Permutation graph]]
|}





[[w:Wolfram Mathematica|Mathematica]] omits the 0 at the end of the inversion vector. Compare [http://www.wolframalpha.com/input/?i=permutation(1+2+5+3+4+6) p1] and [http://www.wolframalpha.com/input/?i=permutation(1+6+4+3+5+2) p2] in [[w:Wolfram Alpha|Wolfram Alpha]].
 <span style="color:gray;">I:</span> p1 = {2,5,4,6,3,1}
 <span style="color:gray;">I:</span> p2 = {6,1,5,3,2,4}
 
 <span style="color:gray;">I:</span> ToInversionVector[p1]
 <span style="color:gray;">O:</span> {5,0,3,1,0}
 <span style="color:gray;">I:</span> ToInversionVector[p2]
 <span style="color:gray;">O:</span> {1,3,2,2,1}
 
 <span style="color:gray;">I:</span> ToOrderedPairs[PermutationGraph[p1]]
 <span style="color:gray;">O:</span> {{2,1},{3,1},{4,1},{5,1},{6,1},{4,3},{5,3},{6,3},{5,4},<span style="color:gray">{1,2},{1,3},{1,4},{1,5},{1,6},{3,4},{3,5},{3,6},{4,5}</span>}
 <span style="color:gray;">I:</span> ToOrderedPairs[PermutationGraph[p2]]
 <span style="color:gray;">O:</span> {{6,1},{3,2},{5,2},{6,2},{5,3},{6,3},{5,4},{6,4},{6,5},<span style="color:gray">{1,6},{2,3},{2,5},{2,6},{3,5},{3,6},{4,5},{4,6},{5,6}</span>}

==Example: All permutations of four elements==
[[File:2-element subsets of 4 elements; array, hexagonal.svg|thumb|160px|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. <small>(The Python script used to create it is shown [http://pastebin.com/KP2F8gUg here].)</small>

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 {{invvect|v}} and left inversion count {{invvect|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:<br>
The nontrivial elements of {{invvect|l}} are the sums of the descending diagonals of the triangle, and those of {{invvect|r}} are the sums of the of the ascending diagonals.<br>


The default order of the table is the reverse colex order by <math>\pi</math>, which is the same as the colex order by {{invvect|l}}. <small>(This header cell is highlighted by a darker gray.)</small>

Lex order by <math>\pi</math> is the same as lex order by {{invvect|r}}.


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

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

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


Note that the set of all {{invvect|r}}, the set of all {{invvect|v}} and the set of all reflected {{invvect|l}} for the same [[w:symmetric group|symmetric group]] are equal.<br>
So sorting by two columns that have the omissible 0 at the same end makes these columns equal.

{| class="collapsible collapsed" style="width: 100%; border: 1px solid #aaa;"
!bgcolor="#f2f2f2"| 3-element permutations
|-
|
{| style="width: 100%;"
| {{3-el perm inversions}}
| {{3-el perm inversions}}
|}
|}

{| style="width: 100%;"
| {{4-el perm inversions}}
| {{4-el perm inversions}}
|}

<small>(A more detailled version of this table, including element-based inversion sets and the unused fourth vector, can be found [[Inversions in sequences#Permutations|'''here''']].)</small>

==Weak order of permutations==

The [[w:Hasse diagram|Hasse diagram]] below in the middle shows the 24 inversion sets ordered by the [[w:Subset|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,<br>
where <math>(\pi, \sigma)</math> is an edge iff <math>i < j ~~ \land ~~ \pi(i)+1 = \pi(j) ~~ \land ~~ (ij) \cdot \pi = \sigma</math>, i.e. when only two elements with consecutive values are swapped.<br>
(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 <math>\le</math> 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).
{| style="width:100%"
|style="vertical-align:top;"| [[File:Symmetric group 4; permutohedron 3D; l-e factorial numbers.svg|thumb|center|500px|Permutations and left inversion counts {{invvect|l}}]]
|style="vertical-align:top;"| [[File:Symmetric group 4; permutohedron 3D; inversions.svg|thumb|center|500px|Inversion sets (place-based)]]
|style="vertical-align:top;"| [[File:Symmetric group 4; permutohedron 3D; Lehmer codes.svg|thumb|center|500px|Permutations and right inversion counts {{invvect|r}}]]
|}

{| class="collapsible collapsed" style="width: 100%; border: 1px solid #aaa;"
!bgcolor="#f2f2f2"| Schlegel diagrams of the permutohedra above
|-
|
{| style="width:100%"
|style="vertical-align:top;"| [[File:Symmetric group 4; permutohedron; l-e factorial numbers.svg|thumb|center|500px|Permutations and left inversion counts {{invvect|l}}]]
|style="vertical-align:top;"| [[File:Symmetric group 4; permutohedron; inversions.svg|thumb|center|500px|Inversion sets (place-based)]]
|style="vertical-align:top;"| [[File:Symmetric group 4; permutohedron; Lehmer codes.svg|thumb|center|500px|Permutations and right inversion counts {{invvect|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 [[w:Cayley graph|Cayley graph]],<br>
where <math>(\pi, \sigma)</math> is an edge iff <math>i+1 = j ~~ \land ~~ \pi(i) < \pi(j) ~~ \land ~~ (ij) \cdot \pi = \sigma</math>, 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.

{| class="collapsible collapsed" style="width: 100%; border: 1px solid #aaa;"
!bgcolor="#f2f2f2"| Cayley graph
|-
|
{| style="width:100%"
|style="vertical-align:top;"| [[File:Symmetric group 4; Cayley graph 1,2,6.svg|thumb|center|500px|Cayley graph as a Schlegel diagram]]
|style="vertical-align:top;width:500px;"|
The Cayley graph on the right shows the inverse permutations of those in the permutohedron above it.

Below their {{invvect|v}} are shown. They are the same vectors as the {{invvect|r}} in the permutohedron above (because the {{invvect|r}}  is the {{invvect|v}} of the inverse permutation).

There are 12 edges of each color, and each represents the swapping of two elements on consecutive places — e.g. blue stands for the swapping of the elements on the first two places.

The six squares of the [[w:Truncated octahedron|truncated octahedron]] have blue and red edges, and the edges connecting the squares are green. Four of the eight hexagons have blue and four have red edges.
|style="vertical-align:top;"| [[File:Symmetric group 4; Cayley graph 1,2,6 (3D).svg|thumb|center|500px|Inverse permutations and inversion vectors {{invvect|v}}]]
|}
|}

=={{rdrdo}} [[Inversions in sequences]]==

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.

{{Template:4-el sequence inversions; permutations of 0011}}

=={{rdrdo}} [[Arrays of permutations]] {{anchor|arrays1}}==
[[File:Array of permutations; transpositions, chains.svg|600px|right]]
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 {{oeis|A211367}}.
<br style="clear: both;">

== {{rdrdo}} [[Walsh permutation; inversions|Walsh permutations]] ==

{| style="width:100%"
|style="vertical-align:top;"|
{{multiple image
 | align = center
 | image1 = Rothe diagram; wp( 4, 8, 1, 2).svg
 | width1 = 250
 | image2 = Inversion set 16; Walsh (4, 8, 1, 2).svg
 | width2 = 232
 | footer = ''wp''(4,8,1,2) = (0,4,8,12, 1,5,9,13, 2,6,10,14, 3,7,11,15)<br><br>{{invvect|r}} = {{invvect|v}} = (0,3,6,9, 0,2,4,6, 0,1,2,3, 0,0,0<span style="opacity: .3;">,0</span>)<br>{{invvect|l}} = (<span style="opacity: .3;">0,</span>0,0,0, 3,2,1,0, 6,4,2,0, 9,6,3,0)
}}
|style="vertical-align:top;"|
{{multiple image
 | align = center
 | image1 = Rothe diagram; wp(14,13,11, 7).svg
 | width1 = 250
 | image2 = Inversion set 16; Walsh (14, 13, 11, 7).svg
 | width2 = 232
 | footer = ''wp''(14,13,11,7) = (0,14,13,3, 11,5,6,8, 7,9,10,4, 12,2,1,15)<br><br>{{invvect|r}} = {{invvect|v}} = (0,13,12,2, 9,3,3,4, 3,3,3,2, 2,1,0<span style="opacity: .3;">,0</span>)<br>{{invvect|l}} = (<span style="opacity: .3;">0,</span>0,1,2, 2,3,3,3, 4,3,3,9, 2,12,13,0)
}}
|style="vertical-align:top;"|
{{multiple image
 | align = center
 | image1 = Rothe diagram; wp(13,11, 7,15).svg
 | width1 = 250
 | image2 = Inversion set 16; Walsh (15, 14, 13, 11).svg
 | width2 = 232
 | footer = ''wp''(13,11, 7,15) = (0,15,14,1, 13,2,3,12, 11,4,5,10, 6,9,8,7)<br><br>{{invvect|r}} = (0,14,13,0, 11,0,0,8, 7,0,0,4, 0,2,1<span style="opacity: .3;">,0</span>)<br>{{invvect|v}} = (0,2,3,3, 5,5,6,8, 7,6,5,4, 3,2,1<span style="opacity: .3;">,0</span>)<br>{{invvect|l}} = (<span style="opacity: .3;">0,</span>0,1,2, 2,3,3,3, 4,5,5,5, 6,6,7,8)
}}
|}

==Sources==
{{multiple image
 | align = right
 | image1 = Cramer derangement.jpg
 | width1 = 229
 | image2 = Rothe Stellenexponenten 2.jpg
 | width2 = 189
}}

===Books===

====Cramer 1750====

[[w:Gabriel Cramer|Cramer]] defines the inversion under the name ''dérangement'' to calculate the [[w:Parity of a permutation|sign]] of a permutation.

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

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

<small>{{cite book | last = Chabert | title = A history of algorithms : from the pebble to the microchip | publisher = Springer | location = Berlin New York | year = 1999 | isbn = 9783540633693 }}
— 9.1 ''Cramers rule'' (p. 286)</small>

====Rothe 1800====

[[w:Heinrich August Rothe|Rothe]] essentially defines the right inversion count {{invvect|r}} under the name ''Stellenexponenten'' — but with each place bigger by 1.<br>

:<math>s_i</math> is the position of <math>\pi_i</math> among the <math>\pi_k</math> with <math>k \ge i</math> in numerical order. <small>([http://www.e-rara.ch/zut/content/pageview/1109826 p. 163])</small>
Strangely he counts from 1 rather than 0, which later leads to avoidable additions and subtractions by 1:
:<math>s_i + 1 = \# \{ \pi_k \mid k>i \land \pi_k<\pi_i \}</math> <small>([http://www.e-rara.ch/zut/content/pageview/1109828 p. 165])</small>
:Each permutation has [[w:Parity of a permutation|sign]] <math>+</math> when the sum of the <math>s_i - 1</math> is even, and sign <math>-</math> when it is odd. <small>([http://www.e-rara.ch/zut/content/pageview/1109829 p. 266])</small>

For the permutation <math>6~4~3~9~8~10~1~7~2~5</math> the ''Stellenexponenten'' are given as <math>6~4~3~6~5~5~1~3~1~1</math>.

[[w:Thomas Muir (mathematician)|Muir]] translates ''Stellenexponent'' as ''place-index'' and calls it “an ill-advised and purposeless modification of Cramers idea of a ‘derangement’”. <small>(''The Theory of the Determinant...'', [https://archive.org/stream/theoryofdetermin01muiruoft#page/n71/mode/2up p. 55])</small>

<small>"[http://astronomie-rara.ethbib.ethz.ch/zut/content/pageview/1341041 Ueber Permutationen, in Beziehung auf die Stellen ihrer Elemente. Anwendung der daraus abgeleiteten Satze auf das Eliminationsproblem]". In [[w:Carl Friedrich Hindenburg|Hindenburg, Carl]], ed., ''Sammlung Combinatorisch-Analytischer Abhandlungen'', pp.&nbsp;263–305, Bey G. Fleischer dem jüngern, 1800.</small>

====Laisant 1888====

After defining the factorial number system [[w:Charles-Ange Laisant|Laisant]] defines the right inversion count {{invvect|r}} under the name ''signe figuratif''.

For the permutation <math>4~3~6~5~1~2</math> the ''signe figuratif'' is given as <math>(3~2~3~2~0)</math>.

<small>{{Citation
 | language=fr
 | last=Laisant
 | first=Charles-Ange
 | title=Sur la numération factorielle, application aux permutations
 | journal=Bulletin de la Société Mathématique de France
 | volume=16
 | issue=
 | year=1888
 | pages=176–183
 | url=http://www.numdam.org/item?id=BSMF_1888__16__176_0
 }}</small>


====Aigner 2007====
{{textbox|{{abbr|p-b perm|Place-based definition for permutations}}}}
<blockquote>
Now we look at permutations of <math>\{1, 2, ..., n\}</math> in word form <math>\sigma = a_1, a_2 ... a_n, a_i = \sigma(i)</math>.<br>
The pair <math>\{i, j\}</math> is called an ''inversion'' if <math>i < j</math> but <math>a_i > a_j</math>.

A moment's thought shows that <math>\{i, j\}</math> is an inversion if and only if the edges <math>ia_i</math> and <math>ja_j</math> cross in the diagram.<br>
Hence the inversion number <math>inv(\sigma)</math> equals the number of crossings.
</blockquote>

<small>{{cite book | last = Aigner | first = Martin | title = A course in enumeration | publisher = Springer | location = Berlin New York | year = 2007 | isbn = 3642072534 }}
— ''Word Representation'' (p. 27 ff)</small>


====Comtet 1974====
{{textbox|{{abbr|p-b perm|Place-based definition for permutations}}}}
<blockquote>
An inversion of a permutation <math>\sigma \in \mathfrak{S}[n]</math> is a pair <math>(i, j)</math> such that <math>1 \le i < j \le n</math> and <math>\sigma(i) > \sigma(j)</math>. In this case we say that <math>\sigma</math> has an inversion in <math>(i, j)</math>.
</blockquote>

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

<small>{{cite book | last = Comtet | first = Louis | title = Advanced combinatorics; the art of finite and infinite expansions | publisher = D. Reidel Pub. Co | location = Dordrecht,Boston | year = 1974 | isbn = 9027704414 }}
— 6.4 ''Inversions of a permutation of [n]'' (p. 237)</small>


====Cormen et al. 2001====
{{textbox|{{abbr|p-b seq|Place-based definition for sequences}}}}
<blockquote>
Let <math>A[1..n]</math> be an array of n distinct numbers. If <math>i < j</math> and <math>A[i] > A[j]</math>, then the pair <math>(i, j)</math> is called an ''inversion'' of <math>A</math>.
</blockquote>

<small>{{cite book | last = Cormen | first = Thomas | title = Introduction to algorithms | publisher = MIT Press | location = Cambridge, Mass | year = 2001 | isbn = 0262531968 }}
— 2-4 ''Inversions'' (p. 41) and 5.2-5 (p. 122)</small>


====Knuth 1973====
{{textbox|{{abbr|e-b perm|Element-based definition for permutations}}<br>{{invvect|v}} as ''inversion table''}}
<blockquote>
If <math>i<j</math> and <math>a_i>a_j</math>, the pair <math>(a_i, a_j)</math> 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).<br>

The ''inversion table'' <math>b_1 b_2 ... b_n</math> of the permutation <math>a_1 a_2 ... a_n</math> is obtained by letting <math>b_j</math> be the number of elements to the left of <math>j</math> that are greater than <math>j</math>.<br>
In other words, <math>b_j</math> is the number of inversions whose second component is <math>j</math>.
</blockquote>

<small>{{cite book | last = Knuth | first = Donald | title = The art of computer programming | publisher = Addison-Wesley Pub. Co | location = Reading, Mass | year = 1973 | isbn = 0201896850 }}
— 5.1.1 ''Inversions'' (p. 11)</small>


====Pemmaraju & Skiena 2003====
{{textbox|{{abbr|e-b perm|Element-based definition for permutations}}<br>{{invvect|v}} as ''inversion vector''}}
<blockquote>
A pair of elements <math>(\pi(i), \pi(j))</math> in a permutation <math>\pi</math> represents an ''inversion'' if <math>i > j</math> and <math>\pi(i) < \pi(j)</math>.<br>
An inversion is a pair of elements that are out of order {{ellipsis}}

For any <math>n</math>-permutation <math>\pi</math>, we can define an ''inversion vector'' <math>v</math> as follows. For each integer <math>i</math>, <math>1 \le i \le n-1</math>, the <math>i</math>th element of <math>v</math> is the number of elements in <math>\pi</math> greater than <math>i</math> to the left of <math>i</math>.
</blockquote>

<small>{{cite book | last = Pemmaraju | first = Sriram | title = Computational discrete mathematics : combinatorics and graph theory with Mathematica | publisher = Cambridge University Press | location = Cambridge, U.K. New York | year = 2003 | isbn = 9780521806862 }}
— 2.2 ''Inversions and Inversion Vectors'' (p. 69)</small>


====Vitter & Flajolet 1990====
{{textbox|{{abbr|e-b perm|Element-based definition for permutations}}<br>{{invvect|v}} as ''inversion table''}}
<blockquote>
An ''inversion'' in permutation <math>\sigma</math> is an “out of order” pair <math>(\sigma_k, \sigma_j)</math> of elements, in which <math>k<j</math> but <math>\sigma_k > \sigma_j</math>.<br>
The number of inversions is thus a measure of the amount of disorder in a permutation.

The ''inversion table'' of the permutation <math>\sigma = \sigma_1 \sigma_2 \dots \sigma_n</math> is the ordered sequence
:<math>b_1, b_2, \dots, b_n</math>, where <math>b_k = \Big| \{ 1 \le j <\sigma_k^-1 | \sigma_j > k \} \Big|</math>.
</blockquote>

<small>{{cite book | last = Leeuwen | first = J | title = Handbook of theoretical computer science | publisher = Elsevier MIT Press | location = Amsterdam New York Cambridge, Mass | year = 1990 | isbn = 9780444880710 }}
— 3.1 ''Inversions'' (p. 459)</small>


====Grätzer 2016====
{{textbox|{{abbr|e-b perm|Element-based definition for permutations}}}}
The authors define the usual strict linear ordering <math>1 < 2 < \cdots < i < i+1 < \cdots < n</math> on <math>[n]</math> as <math>\mathcal{I}_n = \{ ~~ (i, j) \in [n] \times [n] ~~ | ~~ i < j ~~ \}</math>.

<blockquote>
Let <math>\sigma</math> be a permutation on <math>[n]</math>. An ''inversion'' of <math>\sigma</math> is an ordered pair <math>(i, j) \in \mathcal{I}_n</math> satisfying <math>\sigma^{-1}(i) > \sigma^{-1}(j)</math>.<br>
The ''inversion set'' of <math>\sigma</math> is then defined as <math>\mathrm{inv}(\sigma) = \{ ~~ (i, j) \in \mathcal{I}_n ~~ | ~~ \sigma^{-1}(i) > \sigma^{-1}(j) ~~ \}</math>.
</blockquote>

The inversion set of <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{pmatrix}</math> is given as <math>\{(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (4, 5)\}</math>.

In the footnote it is mentioned that other authors often use the definition as an ordered pair <math>(i, j) \in \mathcal{I}_n</math> such that <math>\sigma(i) > \sigma(j)</math>.<br>
TAoCP is given as an example — despite the fact that Knuth uses essentially the same definition (see [[#Knuth 1973|above]]).

<small>{{cite book | last = Gratzer | first = George | title = Lattice theory. special topics and applications | publisher = Birkhäuser | location = Cham, Switzerland | year = 2016 | isbn = 331944235X }}
— 7-2 ''Basic objects'' (p. 221)</small>


====Joshi 1989====
{{textbox|{{abbr|e-b seq|Element-based definition for sequences}}<br>{{invvect|r}} as ''inversion table'' or ''inversion vector''}}
<blockquote>
Let <math>x = x_1 x_2 \dots x_n</math> be a sequence of real numbers.<br>
By an '''inversion''' in <math>x</math>, we mean a pair <math>(x_i, x_j)</math> such that <math>i<j</math> but <math>x_i>x_j</math>.<br>
For each <math>i</math>, let <math>d_i</math> = the number of inversions whose first entry is <math>x_i</math>, i.e.
:<math>d_i = \big| \{ x_j : i < j, x_i > x_j \} \big|</math>.
Then the sequence <math>(d_1 d_2 \dots d_n)</math> is called the '''inversion table''' or '''inversion vector''' of <math>x</math>. {{ellipsis}}<br>
The permutation <math>2~4~3~5~1</math> has <math>(1, 2, 1, 1, 0)</math> as its inversion table.
</blockquote>

<small>{{cite book | last = Joshi | first = K. D. | title = Foundations of discrete mathematics | publisher = Wiley Wiley Eastern Ltd | location = New York New Delhi, India | year = 1989 | isbn = 8122401201 }}
— Definition 3.12 (p. 188)</small>


====Bóna 2012====
{{textbox|{{abbr|e-b perm|Element-based definition for permutations}}}}
Bóna first uses the definition with elements:
<blockquote>
Let <math>p = p_1 p_2 \cdots p_n</math> be a permutation. We say that <math>(p_i , p_j)</math> is an inversion of <math>p</math> if <math>i < j</math> but <math>p_i > p_j</math>.<br>
Permutation 31524 has four inversions, namely (3, 1), (3, 2), (5, 2), and (5,4).
</blockquote>
<small>2.1 ''Inversions'' (p. 43)</small>

{{textbox|{{abbr|p-b seq|Place-based definition for permutations}}}}
But for multisets he uses places instead:
<blockquote>
An inversion of a permutation <math>p = p_1 p_2 \cdots p_n</math> of a multiset is defined just as it was for permutations of sets, that is, <math>(i, j)</math> is a inversion if <math>i < j</math>, but <math>p_i > p_j</math>·<br>
The multiset-permutation 1322 has two inversions, (2, 3), and (2, 4).
</blockquote>
<small>2.2 ''Inversions in Permutations of Multisets'' (p. 57)</small>

The definition of non-inversions also uses places:
<blockquote>
{{ellipsis}} look at all non-inversions of a generic permutation <math>p = p_1 p_2 \cdots p_n</math>; that is, pairs so that <math>i < j</math> and <math>p_i < p_j</math>.
</blockquote>
<small>4.4.1.1 ''An exponential upper bound'' (p. 141)</small>

<small>{{cite book | last = Bóna | first = Miklós | title = Combinatorics of permutations | publisher = CRC Press | location = Boca Raton, FL | year = 2012 | isbn = 1439850518 }}</small>


====Calude et al. 2003====
{{textbox|{{invvect|l}} as ''left-inversion vector''<br>{{invvect|r}} as ''right-inversion vector''}}
<blockquote>
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.<br>
For the permutation <math>(p[i], \dots, p[n])</math> the ''right-inversion vector'' <math>(g[i], \dots, g[n-1])</math> is defined by the rule that <math>g[i]</math> is the number of <math>p[j]</math> to the right of but smaller than <math>p[i]</math>;<br>
in the ''left-inversion vector'', <math>g[i]</math> is the number of <math>p[j]</math> to the left of but larger than <math>p[i]</math>.
</blockquote>
<small>
{{cite book | last = Calude | first = Cristian | title = Discrete mathematics and theoretical computer science : 4th international conference, DMTCS 2003, Dijon, France, July 7-12, 2003 : proceedings | publisher = Springer | location = Berlin New York | year = 2003 | isbn = 3540405054 }}
— ''Generating Gray codes...'' (p. 81)</small>


====Lothaire 2002====
{{textbox|{{abbr|p-b perm|Place-based definition for permutations}}<br>{{invvect|l}} as ''Lehmer encoding''}}
<blockquote>
If <math>\sigma = \sigma(1) \sigma(2) \dots \sigma(k)</math> is <span style="opacity: .3;">[</span>a permutation of <math>[k]</math><span style="opacity: .3;">]</span> an ''inversion'' of <math>\sigma</math> is a pair <math>(i, j)</math> such that <math>1 \le i < j \le k</math> and <math>\sigma(i) > \sigma(j)</math>.
</blockquote>
<small>11.1. ''Prelimiaries'' (p. 367)</small>

<blockquote>
Let <math>\sigma</math> be a permutation of <math>[n]</math>. For <math>1 \le i \le n</math>, let <math>l_i</math> be the number of indices <math>j < i</math> such that <math>\sigma(j) > \sigma(i)</math>. The word <math>l = l_1 l_2 \cdots l_n</math> will be called the ''Lehmer encoding'' of <math>\sigma</math>.

To the permutation <math>\sigma = 6~8~4~5~9~3~1~2~7</math> corresponds the Lehmer encoding <math>l = 0~0~2~2~0~5~6~6~2</math>.
</blockquote>
<small>11.4. ''Inversions of permutations with a given shape'' (p. 372)</small>

<small>{{cite book | last = Lothaire | first = M | author-link = w:M. Lothaire | title = Algebraic combinatorics on words | publisher = Cambridge University Press | location = Cambridge New York | year = 2002 | isbn = 0521812208 }}</small>

===Papers===

====Vajnovszki 2011====
{{textbox|{{abbr|p-b perm|Place-based definition for permutations}}<br>{{invvect|l}} as ''Lehmer code''}}
<blockquote>
The pair <math>(i, j)</math> is an ''inversion'' of <math>\pi \in \mathfrak{S}_n</math> if <math>i < j</math> but <math>\pi_i > \pi_j</math>. {{ellipsis}}

An integer sequence <math>t_1 t_2 \dots t_n</math> is said to be ''subexcedent'' if <math>0 \le t_i \le i - 1</math> for <math>1 \le i \le n</math>, and the set of lenth-<math>n</math> subexcedent sequences is denoted by <math>S_n</math> {{ellipsis}}.<br>
The ''Lehmer code'' [5] is a bijection code : <math>\mathfrak{S}_n \rightarrow S_n</math> which maps each permutation <math>\pi = \pi_1 \pi_2 \dots \pi_n</math> to a subexcedent sequence <math>t_1 t_2 \dots t_n</math><br>
where, for all <math>i, ~ 1 \le i \le n</math>, <math>~ t_i</math> is the number of inversions <math>(j, i)</math> in <math>\pi</math> (or equivalently, the number of entries in <math>\pi</math> larger than <math>\pi_i</math> and on its left).<br>
<small>[5] &nbsp;&nbsp;&nbsp;&nbsp; D. H. Lehmer, Teaching combinatorial tricks to a computer, in Proc. Sympos. Appl. Math., 10 (1960), Amer. Math. Soc., 179-193.</small>
</blockquote>
<small>Vajnovszki. [http://www.sciencedirect.com/science/article/pii/S0166218X11001946 ''A new Euler–Mahonian constructive bijection''] — pp. 1-2</small>


====Gnedin & Olshanski 2012====
{{textbox|{{abbr|p-b perm|Place-based definition for permutations}}<br>{{invvect|l}} as ''left inversion count''<br>{{invvect|r}} as ''right inversion count''}}
<blockquote>
For <math>\sigma \in \mathfrak{S}</math>, a pair of positions <math>(i, j) \in \mathbb{Z} \times \mathbb{Z}</math> is an ''inversion'' in <math>\sigma</math> if <math>i < j</math> and <math>\sigma(i) > \sigma(j)</math>.<br>
If <math>(i, j)</math> is an inversion, we say that it is a ''left inversion'' for <math>j</math>, and a ''right inversion'' for <math>i</math>.<br>
Introduce the counts of left and right inversions,
:<math>\mathcal{l}_i := \# \{j: j < i, \sigma(j) > \sigma(i) \}, ~~~~ \mathcal{r}_i := \# \{j: j > i, \sigma(j) < \sigma(i) \}, ~~~~ i \in \mathbb{Z}</math>,
respectively (of course, for the general <math>\sigma \in \mathfrak{S}</math> these quantities may be infinite).
</blockquote>
<small>4. ''A construction from independent geometric variables'' (p. 624)</small>

The authors proof the following formula for balanced permutations, which include finite permutations:
:<math>\sigma(i) =  i + \mathcal{r}_i - \mathcal{l}_i, ~~~~ i \in \mathbb{Z}</math>
<small>Lemma 4.6 (p. 627)</small>

<small>Gnedin; Olshanski. [http://www.sciencedirect.com/science/article/pii/S0196885812000115 ''The two-sided infinite extension of the Mallows model for random permutations'']</small>


====Deutsch et al. 2008====
{{textbox|{{abbr|p-b perm|Place-based definition for permutations}}<br>{{invvect|r}} as ''right inversion vector''}}
<blockquote>
In a permutation <math>\pi = \pi_1 \pi_2 \dots \pi_n</math>, an ''inversion'' is a pair <math>i < j</math> such that <math>\pi_i>\pi_j</math>. {{ellipsis}}<br>
If <math>c_i</math> is the number of <math>j > i</math> with <math>\pi_j < \pi_i</math>, then <math>(c_1, c_2, \dots, c_n)</math> is called the ''right inversion vector'' of <math>\pi</math> {{ellipsis}}.
</blockquote>

<small>Deutsch; Pergola; Pinzani. [https://arxiv.org/abs/0810.2876 ''Six bijections between deco polyominoes and permutations'']
— p. 5</small>


====Barth & Mutzel 2004====
{{textbox|{{abbr|e-b seq|Element-based definition for sequences}}}}
[[File:Bilayer cross counting, non-map.svg|thumb|Crossings in a bilayer graph...]]
[[File:Bilayer cross counting, non-bijective map.svg|thumb|...correspond to inversions of a non-bijective map.]]
<blockquote>
In a sequence <math>\pi = \langle a_0, a_1, \dots , a_{t-1} \rangle</math> of pairwise comparable elements <math>a_i ~ (i = 0, 1, \dots , t-1)</math>, a pair <math>(a_i, a_j)</math> is called an ''inversion'' if <math>i < j</math> and <math>a_i > a_j</math>.
</blockquote>

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.<br>
In this example the map is <math>\pi = \langle 0,1,2,0,3,4,0,2,3,2,4 \rangle</math>.

<math>\pi_2 = 2</math>, <math>\pi_3 = 0</math> and <math>\pi_6 = 0</math>, so with the place-based definition the sequence would have the inversions <math>(2, 3)</math> and <math>(2, 6)</math>.<br>
With the element-based definition, chosen by the authors, one could say that the sequence has the inversion <math>(2, 0)</math> twice.

<small>{{cite journal |ref = harv
 | first1 = Wilhelm | last1 = Barth
 | first2 = Petra | last2 = Mutzel |author2-link = w:Petra Mutzel
 | title = Simple and Efficient Bilayer Cross Counting
 | journal = Journal of Graph Algorithms and Applications | volume = 8 | issue = 2 | pages = 179&ndash;194 | year = 2004 | doi = 10.7155/jgaa.00088}}
— 2 ''Bilayer Cross Counts and Inversion Numbers'' (p. 183)</small>
<br style="clear: both;">

[[Category:Inversion (discrete mathematics)| ]]
[[Category:Permutations]]