Inversion (discrete mathematics): Difference between revisions

Revision as of 23:13, 28 September 2022

Revision as of 18:20, 29 September 2022

Line 9:

===Inversion===

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

LetThere is an '''inversion''' of <math>\pi</math> bebetween a<math>i</math> [[permutation]].and <math>j</math> Ifif <math>i < j</math> and <math>\pi(i) > \pi(j)</math>,. either theThe inversion is indicated by an ordered pair ofcontaining either the places <math>(i, j)</math>{{sfn|Aigner|2007|pp=27}}{{sfn|Comtet|1974|pp=237}} or the pair of 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}}. is calledWhich value of an '''inversion'''s ofordered <math>\pi</math>pair is smaller indicates whether place-based notation (first value smaller) or value-based notation (second value smaller) is being used.

The '''inversion set''' is the set of all inversions. A permutation's inversion set according to the place-based definitionnotation is that of the [[Permutation#Product and inverse|inverse]] permutation's inversion set according to the element-based definitionnotation, and vice versa,{{sfn|Gratzer|2016|pp=221}} just with the elements of the pairs exchanged.

The inversion is 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>.

The inversionInversion is 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>.

For sequences, inversions according to the element-based definition are not unique, because different pairs of places may have the same pair of values.

For sequences, inversions according to the element-based definition are not unique, because different pairs of places may have the same pair of values.

The '''inversion set''' is the set of all inversions. A permutation's inversion set according to the place-based definition is that of the [[Permutation#Product and inverse|inverse]] permutation's inversion set according to the element-based definition, and vice versa,{{sfn|Gratzer|2016|pp=221}} just with the elements of the pairs exchanged.

===Inversion number===