Inversion (discrete mathematics): Difference between revisions

Revision as of 19:49, 29 September 2022

Revision as of 20:54, 29 September 2022

Line 12:

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}}. 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 according to theusing place-based notation is thatthe ofsame as the [[Permutation#Product and inverseDefinition|inverse permutation's]] inversion set using element-based notation with the elements of each pair exchanged. Likewise, a permutation's inversion set accordingusing toelement-based notation is the elementsame as the inverse permutation's inversion set using place-based notation, andwith vicethe versa,elements of each pair exchanged.{{sfn|Gratzer|2016|pp=221}} just with the elements of the pairs exchanged.

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