Inversions in sequences

Inversion (discrete mathematics)

This page shows the 44 = 256 sequences of length 4 with possible entries from 0...3. These are the integers 0...255 in base 4.

It shows their place-based and element based inversion sets, and all four possible vectors related to them.
l and r are the left and right inversion counts, and v is the inversion vector. The fourth possible vector is unused, but added as u for completeness' sake.

While inversion sets and the related vectors uniquely define permutations, this is not true for sequences in general.

The place-based inversion sets are the same as those of permutations.
There are 35 sequences with the inversion set of permutation , while that of is unique.
The inversion sets of the permutations , , , , , , , , , and appear 15 times each, while those of , , , , , , , , , and appear 5 times each.

The element-based inversion sets are multisets, as different pairs of places can have the same pair of elements.
There are 103 different multisets, corresponding to 40 different inversion vectors v.
So there are 40 − 24 = 16 inversion vectors that permutations can not have — e.g. (4, 0, 0, 0), (0, 3, 0, 0) and (0, 0, 2, 0).

Permutations edit

Place based inversion sets edit

List edit

All sequences

Template:8-el sequence inversions