Inversion (discrete mathematics): Difference between revisions

Revision as of 20:54, 29 September 2022

Revision as of 22:23, 29 September 2022

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 elementss <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}}. Which value of an inversion's ordered pair is smaller indicates whether place-based notation (first value smaller) or element-based notation (second value smaller) is being used.

The '''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 elements of each 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 elements of each pair exchanged.{{sfn|Gratzer|2016|pp=221}}

InversionInversions isare 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.