Content deleted Content added
Citation bot (talk | contribs) Alter: isbn. Add: s2cid, isbn. Upgrade ISBN10 to ISBN13. | You can use this bot yourself. Report bugs here. | Suggested by Abductive | Category:Order theory | via #UCB_Category 145/180 |
Dokidaki-ylc (talk | contribs) m Minor fix to improve readability; add link for cardinality |
||
Line 8:
Let <math>\pi</math> be a [[permutation]]. If <math>i < j</math> and <math>\pi(i) > \pi(j)</math>, either the pair of 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 called an '''inversion''' of <math>\pi</math>.
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>.▼
▲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.
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.
Line 17 ⟶ 16:
===Inversion number===
The '''inversion number''' is the [[cardinality]] of inversion set. It is a common measure of the sortedness of a permutation{{sfn|Vitter|Flajolet|1990|pp=459}} or sequence.{{sfn|Barth|Mutzel|2004|pp=183}}
It is the number of crossings in the arrow diagram of the permutation,{{sfn|Gratzer|2016|pp=221}} its [[Kendall tau distance]] from the identity permutation, and the sum of each of the inversion related vectors defined below.
Line 32 ⟶ 31:
[[File:Inversion example; Rothe 1.svg|thumb|Rothe diagram]]
'''Inversion vector <math>v</math>:'''<br>With the ''element-based'' definition <math>v(i)</math> is the number of inversions whose ''smaller'' (right) component is <math>i</math>.{{sfn|Knuth|1973|pp=11}}
:<math>v(i)</math> is the number of elements in <math>\pi</math> greater than <math>i</math> before <math>i</math>.
:<math>v(i) ~~=~~ \# \{ k \mid k > i ~\land~ \pi^{-1}(k) < \pi^{-1}(i) \}</math>
'''Left inversion count <math>l</math>:'''<br>With the ''place-based'' definition <math>l(i)</math> is the number of inversions whose ''bigger'' (right) component is <math>i</math>.
:<math>l(i)</math> is the number of elements in <math>\pi</math> greater than <math>\pi(i)</math> before <math>\pi(i)</math>.
:<math>l(i) ~~=~~ \# \left\{ k \mid k < i ~\land~ \pi(k) > \pi(i) \right\}</math>
'''Right inversion count <math>r</math>, often called ''[[Lehmer code]]'':'''<br>With the ''place-based'' definition <math>r(i)</math> is the number of inversions whose ''smaller'' (left) component is <math>i</math>.
:<math>r(i)</math> is the number of elements in <math>\pi</math> smaller than <math>\pi(i)</math> after <math>\pi(i)</math>.
:<math>r(i) ~~=~~ \# \{ k \mid k > i ~\land~ \pi(k) < \pi(i) \}</math>
| |||