Inversion (discrete mathematics): Difference between revisions

Revision as of 16:00, 1 October 2022

Revision as of 16:13, 1 October 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 sortedness (sometimes called presortedness) 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 even n and letting <math>m=n/2</math>, <math>\mathtt{inv}(\langle m+1,m+2,\dots,2m,1,2,\dots, m\rangle)=m^2</math> as(because each pair <math>(1\le i\le m < j\le 2m)</math> is an inversion). This last example shows that a set that is intuitively "nearly-sorted" 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.