Inversion (discrete mathematics): Difference between revisions

Revision as of 17:51, 2 October 2022

Latest revision as of 21:04, 16 July 2025

(6 intermediate revisions by 6 users not shown)

Line 10:

Let <math>\pi</math> be a [[permutation]].

There is an '''inversion''' of <math>\pi</math> between <math>i</math> and <math>j</math> if <math>i < j</math> and <math>\pi(i) > \pi(j)</math>. The inversion is indicated by an ordered pair containing either the places <math>(i, j)</math>{{sfn|Aigner|2007|pp=27}}{{sfn|Comtet|1974|pp=237}} or the elements <math>\bigl(\pi(i), \pi(j)\bigr)</math>.{{sfn|Knuth|1973|pp=11}}{{sfn|Pemmaraju|Skiena|2003|pp=69}}{{sfn|Vitter|Flajolet|1990|pp=459}}.

The [[Inversion_(discrete_mathematics)#Example:_All_permutations_of_four_elements|inversion set]] is the set of all inversions. A permutation's inversion set using place-based notation is the same as the [[Permutation#Definition|inverse permutation's]] inversion set using element-based notation with the two components of each ordered pair exchanged. Likewise, a permutation's inversion set using element-based notation is the same as the inverse permutation's inversion set using place-based notation with the two components of each ordered pair exchanged.{{sfn|Gratzer|2016|pp=221}}

Inversions are usually defined for permutations, but may also be defined for sequences:<br>Let <math>S</math> be a [[sequence]] (or [[multiset]] permutation{{sfn|Bóna|2012|pp=57}}). If <math>i < j</math> and <math>S(i) > S(j)</math>, either the pair of places <math>(i, j)</math>{{sfn|Bóna|2012|pp=57}}{{sfn|Cormen|Leiserson|Rivest|Stein|2001|pp=39}} or the pair of elements <math>\bigl(S(i), S(j)\bigr)</math>{{sfn|Barth|Mutzel|2004|pp=183}} is called an inversion of <math>S</math>.

Line 22:

The '''inversion number''' <math>\mathtt{inv}(X)</math>{{sfn|Mannila|1985}} of a sequence <math>X=\langle x_1,\dots,x_n\rangle</math>, is the [[cardinality]] of the inversion set. It is a common measure of sortedness (sometimes called presortedness) of a permutation{{sfn|Vitter|Flajolet|1990|pp=459}} or sequence.{{sfn|Barth|Mutzel|2004|pp=183}} The inversion number is between 0 and <math>\frac{n(n-1)}2</math> inclusive. A permutation and its inverse have the same inversion number.

For example <math>\mathtt{inv}(\langle1,2,\dots, n\rangle)=0</math> since the sequence is ordered. Also, for even n and lettingwhen <math>mn =n/2 2m</math> is even, <math>\mathtt{inv}(\langle m+1,m+2,\dots,2m,1,2,\dots, m\rangle)=m^2</math> (because each pair <math>(1\le i\le m < j\le 2m)</math> is an inversion). This last example shows that a set that is intuitively "nearly- sorted" can still have a quadratic number of inversions.

The inversion number is the number of crossings in the arrow diagram of the permutation,{{sfn|Gratzer|2016|pp=221}} the permutation's [[Kendall tau distance]] from the identity permutation, and the sum of each of the inversion related vectors defined below.

Line 71:

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 (order)|lattice]].

The [[Hasse diagram]] of the inversion sets ordered by the [[subset]] relation forms the [[skeleton (topology)|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.

Line 79:

== See also ==

{{wikiversity|Inversion (discrete mathematics)}}

{{Commons category|Inversion (discrete mathematics)}}

* [[Factorial number system]]

* [[Permutation graph]]

* [[Permutation group#Transpositions, simple transpositions, inversions and sorting|Transpositions, simple transpositions, inversions and sorting]]

* [[Damerau–Levenshtein distance]]

* [[Parity of a permutation]]

Line 121 ⟶ 119:

|url = https://archive.org/details/Comtet_Louis_-_Advanced_Coatorics

| chapter = 6.4 Inversions of a permutation of [n]

| publisher = D. Reidel Pub. Co | ___location = Dordrecht, Boston | year = 1974 | isbn = 9027704414 }}

* {{cite book

| first1=Thomas H. |last1=Cormen |authorlink1=Thomas H. Cormen

Line 143 ⟶ 141:

|title=Algorithm Design

|year=2005

|publisher=Pearson/Addison-Wesley

|isbn=0-321-29535-8 }}

* {{cite book

Line 177 ⟶ 176:

=== Further reading ===

{{refbegin}}

* {{cite journal|journal=Journal of Integer Sequences|volume=4|year=2001|title=Permutations with Inversions|first=Barbara H.|last=Margolius|page=24|bibcode=2001JIntS...4...24M}}

{{refend}}