Inversion (discrete mathematics)

In computer science and discrete mathematics, an inversion in a sequence is a pair of elements that are out of their natural order. Let be a permutation. There is an inversion of between and if and . The inversion is indicated by an ordered pair containing either the places or the elements . The inversion set is the set of all inversions. A permutation's inversion set using place-based notation is the same as the inverse permutation's inversion set using element-based notation with the two components of each ordered pair exchanged. Likewise, a permutation's inversion set using element-based notation is the same as the inverse permutation's inversion set using place-based notation with the two components of each ordered pair exchanged. Inversions are usually defined for permutations, but may also be defined for sequences:Let be a sequence (or multiset permutation). If and , either the pair of places or the pair of elements is called an inversion of . 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 number of a sequence , is the cardinality of the inversion set. It is a common measure of sortedness (sometimes called presortedness) of a permutation or sequence. The inversion number is between 0 and inclusive. A permutation and its inverse have the same inversion number. For example since the sequence is ordered. Also, when is even, (because each pair 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, the permutation's Kendall tau distance from the identity permutation, and the sum of each of the inversion related vectors defined below. Other measures of sortedness include the minimum number of elements that can be deleted from the sequence to yield a fully sorted sequence, the number and lengths of sorted "runs" within the sequence, the Spearman footrule (sum of distances of each element from its sorted position), and the smallest number of exchanges needed to sort the sequence.