A pair of elements is called an inversion in a permutation if and (Skiena 1990, p. 27; Pemmaraju and Skiena 2003,
p. 69). For example, in the permutation contains the four inversions , , , and . Inversions are pairs which are out of order, and are
important in sorting algorithms (Skiena 1990, p. 27).
The total number of inversions can be obtained by summing the elements of the inversion vector. The number of inversions in any
permutation is the same as the number of interchanges
of consecutive elements necessary to arrange them in their natural order (Muir
1960, p. 1). The value can be found in the Wolfram
Language using Signature[p].
The number of inversions in a permutation is equal to that of its inverse permutation (Skiena 1990, p. 29; Knuth 1998). If, from
any permutation, another is formed by interchanging two elements, then the difference
between the number of inversions in the two is always an odd
number.
is called an inversion in a permutation 
if 
and 
(Skiena 1990, p. 27; Pemmaraju and Skiena 2003,
p. 69). For example, in the permutation 
contains the four inversions 
, 
, 
, and 
. Inversions are pairs which are out of order, and are
important in sorting algorithms (Skiena 1990, p. 27).
can be found in the Wolfram
Language using Signature[p].
