The number of inversions in the permutation
Inversions in combinatorics are the number of pairs of elements in which the next element has a smaller number than the previous one. Sometimes it is important to have a quantitative assessment of the degree of difference between an arbitrary permutation and the lexographically smallest one in terms of the number of violations of the increasing order of values of its elements. Any pair of elements where there is such a violation of their mutual position in a permutation is called an inversion.
.Inversions of permutations
For compact recording of inversions by elements of a permutation, the inversion vector is used (V1,…Vj,…Vn) and the inversion table (W1,…Wj,…Wn).
These two forms of notation identify the inversion numbers for all elements of the permutation.
The composition of the vector and the inversion table for digital permutation P=(5,9,1,8,2,6,4,7,3) it is shown in the following example, where the positions of all elements are indexed for clarity:
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | pj | 5 | 9 | 1 | 8 | 2 | 6 | 4 | 7 | 3 | Vj | 0 | 0 | 2 | 1 | 3 | 2 | 4 | 2 | 6 | Wj | 2 | 3 | 6 | 4 | 0 | 2 | 2 | 1 | 9 |
In particular, in this example V8=2, because to the left of the element P8=7 there are 2 elements in the permutation P2=9 and P4=8 with a greater value than 7. On the other hand, W8=1,because to the left of the element with the value 8 (this is P4) there is only 1 element in the permutation (P2=9), the value of which is greater than 8. Similarly, it is possible to justify the choice of the values of the remaining components of the vector and the inversion table in this example. It should also be noted that for any permutation, the values of the components of the vector and the inversion table are related by the following relations:
V1 = Wn = 0; Vj = Wi | i = Pj; Wj = Vi | Pi = j.
Returning to the integral estimates, it should be noted that the sum of the values of all the components of the vector or the inversion table determines the total number of inversions of the I permutation. In particular, for the example considered, it is equal to 20:
I(5, 9, 1, 8, 2, 6, 4, 7, 3) = 20.