Inversion (kombinatorik)

Inversion set and vector of a permutation.svg

Example of inversions of a permutation

The example permutation (4,1,5,2,6,3) has the left inversion count (0,1,0,2,0,3)
and the inversion set { (1,2) , (1,4),(3,4) , (1,6),(3,6),(5,6) }.
The left inversion count converted to decimal is 373 - the permutation's reverse colexicographic rank.

(This permutation is also shown in this array.)

The inversion set contains 6 of the ${\displaystyle {\tbinom {6}{2}}}$ = 15 2-subsets of a 6-set.

The triangle is ordered like the square array  A018900 (compare this triangle).

Inversion set 16; Walsh (15, 14, 13, 11).svg
Den här table skapades med bin2svg.

Inversion qtl1.svg
Författare/Upphovsman: Quartl, Licens: CC BY-SA 3.0
Illustration of an inversion of a permutation.

Symmetric group 4; Cayley graph 1,2,6 (3D).svg

Cayley graph of S₄ generated by the transpositions that swap neighbouring elements

Below the permutations the inversion vectors are shown. Their bitwise-smaller relation corresponds to the edges.

This SVG was created with Inkscape.