Inversion (discrete mathematics): Difference between revisions

Revision as of 19:07, 29 September 2022

Revision as of 19:29, 29 September 2022

Line 22:

The '''inversion number''' <math>\mathtt{inv}(X)</math>{{sfn|Mannila|1985}} of a sequence <math>X=\langle x_1,\dots,x_n\rangle</math>, is the [[cardinality]] of the inversion set. It is a common [[measure of presortedness|measures of (pre-)sortedness]] of a permutation{{sfn|Vitter|Flajolet|1990|pp=459}} or sequence.{{sfn|Barth|Mutzel|2004|pp=183}} The inversion number is between 0 and <math>\frac{n(n-1)}2</math> inclusive. A permutation and its inverse have the same inversion number.

For example <math>\mathtt{inv}(\langle1,2,\dots, n\rangle)=0</math> since the sequence is ordered. Also, for <math>m=n/2</math>, <math>\mathtt{inv}(\langle nm+1,nm+2,\dots,2n2m,1,2,\dots, nm\rangle)=nm^2</math> as each pair <math>(1\le i\le nm < j\le 2n2m)</math> is an inversion. This last example shows that a set that is intuitively "nearly" sorted can still have a quadratic number of inversions.

The inversion number is the number of crossings in the arrow diagram of the permutation,{{sfn|Gratzer|2016|pp=221}} the permutation's [[Kendall tau distance]] from the identity permutation, and the sum of each of the inversion related vectors defined below.