Inversion (discrete mathematics): Difference between revisions

Revision as of 17:54, 2 October 2022

Revision as of 08:26, 9 October 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 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>.