Inversions in sequences

Inversion (discrete mathematics) Template:Rdrup

This page shows the 4⁴ = 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.
Template:Invvect and Template:Invvect are the left and right inversion counts, and Template:Invvect is the inversion vector. The fourth possible vector is unused, but added as Template:Invvect 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 $0$, while that of $23$ is unique.
The inversion sets of the permutations $1$, $2$, $3$, $4$, $6$, $8$, $9$, $12$, $13$, $16$ and $18$ appear 15 times each, while those of $5$, $7$, $10$, $11$, $14$, $15$, $17$, $19$, $20$, $21$ and $22$ 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 Template:Invvect.
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

24 permutations of 0 1 2 3

This list is like the one in the inversion article, but more detailed. Srev colex = Template:Invvectcolex            Slex = Template:Invvectlex Template:Invvectcolex = inverses of Srev colex = Template:Oeis(0..23)            Template:Invvectlex = inverses of Slex This table also allows to sort by the inversion sets. The column to the left of the images brings them in lex order, the right one in colex order. p-blex = Template:Invvectlex            e-blex = Template:Invvectlex            p-bcolex = (0, 1, 3, 2, 4, 5, 9...) = Template:Oeis(0..23) The unlabelled columns on the right bring the permutations in the orders generated by Heap's and Steinhaus–Johnson–Trotter algorithm. The former is (0, 1, 3, 2, 4, 5, 11...) = Template:Oeis(0..23). The latter is (0, 6, 8, 9, 15, 14, 12...) = Template:Oeis(4, 0..23).

12 permutations of 0 0 1 3
These are essentially the the 12 permutations of 1 1 2 4 Narayana has listed in reverse colex order in Ganita Kaumudi, as mentioned by Knuth in volume 4 of TAoCP. Template:Cite book — The work of Narayana (p. 62) Singh, Parmanand (1998): "The Ganita Kaumudi of Narayana Pandita" — Expansion (i.e., Serial Arrangement of Permutations) (p. 47)

6 permutations of 0 0 1 1

Place based inversion sets

15 sequences with inversion set 1
These 15 sequences have the place-based inversion set of permutation $1$ in common, i.e. $\{(0,1)\}$ or . Thus Template:Invvect = (0, 1, 0, 0) and Template:Invvect = (1, 0, 0, 0).

5 sequences with inversion set 5
These 5 sequences have the place-based inversion set of permutation $5$ in common, i.e. $\{(0,1),(0,2),(1,2)\}$ or . Thus Template:Invvect = (0, 1, 2, 0) and Template:Invvect = (2, 1, 0, 0).