Inversions in sequences

Inversion (discrete mathematics)

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.
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 ${\mathit {0}}$, while that of ${\mathit {23}}$ is unique.
The inversion sets of the permutations ${\mathit {1}}$, ${\mathit {2}}$, ${\mathit {3}}$, ${\mathit {4}}$, ${\mathit {6}}$, ${\mathit {8}}$, ${\mathit {9}}$, ${\mathit {12}}$, ${\mathit {13}}$, ${\mathit {16}}$ and ${\mathit {18}}$ appear 15 times each, while those of ${\mathit {5}}$, ${\mathit {7}}$, ${\mathit {10}}$, ${\mathit {11}}$, ${\mathit {14}}$, ${\mathit {15}}$, ${\mathit {17}}$, ${\mathit {19}}$, ${\mathit {20}}$, ${\mathit {21}}$ and ${\mathit {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 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

24 permutations of 0 1 2 3

This list is like the one in the inversion article, but more detailed. Srev colex = lcolex            Slex = rlex ucolex = inverses of Srev colex =  A056019(0..23)            vlex = 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 = llex            e-blex = ulex            p-bcolex = (0, 1, 3, 2, 4, 5, 9...) =  A211363(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...) =  A280318(0..23). The latter is (0, 6, 8, 9, 15, 14, 12...) =  A280319(4, 0..23). 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 S # l p-b r u e-b v 27 0 0123 3210 0 0000 0000 . .. ... ... .. . 0000 0000 0000 0000 . .. ... ... .. . 0000 0000 0 0 30 6 0132 2310 1 1000 0001 . .. ..1 1.. .. . 0010 0100 1000 0001 . .. ..1 1.. .. . 0010 0100 11 1 39 2 0213 3120 1 0100 0010 . .1 ... ... 1. . 0100 0010 0100 0010 . .1 ... ... 1. . 0100 0010 3 7 45 12 0231 1320 2 2000 0002 . .. .11 11. .. . 0110 0110 1100 0011 . .1 .1. .1. 1. . 0200 0020 12 6 54 8 0312 2130 2 1100 0011 . .1 .1. .1. 1. . 0200 0020 2000 0002 . .. .11 11. .. . 0110 0110 8 2 57 14 0321 1230 3 2100 0012 . .1 .11 11. 1. . 0210 0120 2100 0012 . .1 .11 11. 1. . 0210 0120 15 5 75 1 1023 3201 1 0010 0100 1 .. ... ... .. 1 1000 0001 0010 0100 1 .. ... ... .. 1 1000 0001 1 23 78 7 1032 2301 2 1010 0101 1 .. ..1 1.. .. 1 1010 0101 1010 0101 1 .. ..1 1.. .. 1 1010 0101 10 22 99 4 1203 3021 2 0200 0020 . 11 ... ... 11 . 1100 0011 0110 0110 1 1. ... ... .1 1 2000 0002 4 16 108 18 1230 0321 3 3000 0003 . .. 111 111 .. . 1110 0111 1110 0111 1 1. 1.. ..1 .1 1 3000 0003 23 17 114 10 1302 2031 3 1200 0021 . 11 .1. .1. 11 . 1200 0021 2010 0102 1 .. 1.1 1.1 .. 1 2010 0102 7 21 120 20 1320 0231 4 3100 0013 . .1 111 111 1. . 1210 0121 2110 0112 1 1. 1.1 1.1 .1 1 3010 0103 20 18 135 3 2013 3102 2 0110 0110 1 1. ... ... .1 1 2000 0002 0200 0020 . 11 ... ... 11 . 1100 0011 2 8 141 13 2031 1302 3 2010 0102 1 .. 1.1 1.1 .. 1 2010 0102 1200 0021 . 11 .1. .1. 11 . 1200 0021 13 9 147 5 2103 3012 3 0210 0120 1 11 ... ... 11 1 2100 0012 0210 0120 1 11 ... ... 11 1 2100 0012 5 15 156 19 2130 0312 4 3010 0103 1 .. 111 111 .. 1 2110 0112 1210 0121 1 11 1.. ..1 11 1 3100 0013 22 14 177 16 2301 1032 4 2200 0022 . 11 11. .11 11 . 2200 0022 2200 0022 . 11 11. .11 11 . 2200 0022 16 10 180 22 2310 0132 5 3200 0023 . 11 111 111 11 . 2210 0122 2210 0122 1 11 11. .11 11 1 3200 0023 19 13 198 9 3012 2103 3 1110 0111 1 1. 1.. ..1 .1 1 3000 0003 3000 0003 . .. 111 111 .. . 1110 0111 9 3 201 15 3021 1203 4 2110 0112 1 1. 1.1 1.1 .1 1 3010 0103 3100 0013 . .1 111 111 1. . 1210 0121 14 4 210 11 3102 2013 4 1210 0121 1 11 1.. ..1 11 1 3100 0013 3010 0103 1 .. 111 111 .. 1 2110 0112 6 20 216 21 3120 0213 5 3110 0113 1 1. 111 111 .1 1 3110 0113 3110 0113 1 1. 111 111 .1 1 3110 0113 21 19 225 17 3201 1023 5 2210 0122 1 11 11. .11 11 1 3200 0023 3200 0023 . 11 111 111 11 . 2210 0122 17 11 228 23 3210 0123 6 3210 0123 1 11 111 111 11 1 3210 0123 3210 0123 1 11 111 111 11 1 3210 0123 18 12

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. Knuth, Donald (2005). "7.2.1.7 History and further references". The art of computer programming. Addison-Wesley. ISBN 0321335708.  — The work of Narayana (p. 62) Singh, Parmanand (1998): "The Ganita Kaumudi of Narayana Pandita" — Expansion (i.e., Serial Arrangement of Permutations) (p. 47) 0 1 2 3 4 5 6 7 8 9 10 11 S # l p-b r u e-b v 7 0013 3100 0 0000 0000 . .. ... ... .. . 0000 0000 0000 0000 . .. ... ... .. . 0000 0000 13 0031 1300 1 1000 0001 . .. ..1 1.. .. . 0010 0100 1000 0001 . .. .1. .1. .. . 0100 0010 19 0103 3010 1 0100 0010 . .1 ... ... 1. . 0100 0010 0010 0100 1 .. ... ... .. 1 1000 0001 28 0130 0310 2 2000 0002 . .. .11 11. .. . 0110 0110 1010 0101 1 .. 1.. ..1 .. 1 2000 0002 49 0301 1030 2 1100 0011 . .1 .1. .1. 1. . 0200 0020 2000 0002 . .. 11. .11 .. . 1100 0011 52 0310 0130 3 2100 0012 . .1 .11 11. 1. . 0210 0120 2010 0102 1 .. 11. .11 .. 1 2100 0012 67 1003 3001 2 0110 0110 1 1. ... ... .1 1 2000 0002 0020 0200 2 .. ... ... .. 2 2000 0002 76 1030 0301 3 2010 0102 1 .. 1.1 1.1 .. 1 2010 0102 1020 0201 2 .. 1.. ..1 .. 2 3000 0003 112 1300 0031 4 2200 0022 . 11 11. .11 11 . 2200 0022 2020 0202 2 .. 2.. ..2 .. 2 4000 0004 193 3001 1003 3 1110 0111 1 1. 1.. ..1 .1 1 3000 0003 3000 0003 . .. 21. .12 .. . 2100 0012 196 3010 0103 4 2110 0112 1 1. 1.1 1.1 .1 1 3010 0103 3010 0103 1 .. 21. .12 .. 1 3100 0013 208 3100 0013 5 2210 0122 1 11 11. .11 11 1 3200 0023 3020 0203 2 .. 21. .12 .. 2 4100 0014

6 permutations of 0 0 1 1

0 1 2 3 4 5 S # l p-b r u e-b v 5 0011 1100 0 0000 0000 . .. ... ... .. . 0000 0000 0000 0000 . .. ... ... .. . 0000 0000 17 0101 1010 1 0100 0010 . .1 ... ... 1. . 0100 0010 0010 0100 1 .. ... ... .. 1 1000 0001 20 0110 0110 2 2000 0002 . .. .11 11. .. . 0110 0110 0020 0200 2 .. ... ... .. 2 2000 0002 65 1001 1001 2 0110 0110 1 1. ... ... .1 1 2000 0002 0020 0200 2 .. ... ... .. 2 2000 0002 68 1010 0101 3 2010 0102 1 .. 1.1 1.1 .. 1 2010 0102 0030 0300 3 .. ... ... .. 3 3000 0003 80 1100 0011 4 2200 0022 . 11 11. .11 11 . 2200 0022 0040 0400 4 .. ... ... .. 4 4000 0004

Place based inversion sets

15 sequences with inversion set 1

These 15 sequences have the place-based inversion set of permutation ${\mathit {1}}$ in common, i.e. $\{(0,1)\}$ or . Thus l = (0, 1, 0, 0) and r = (1, 0, 0, 0). 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 S # u e-b v 69 1011 1101 3 0010 0100 1 .. ... ... .. 1 1000 0001 70 1012 2101 4 0010 0100 1 .. ... ... .. 1 1000 0001 71 1013 3101 5 0010 0100 1 .. ... ... .. 1 1000 0001 74 1022 2201 5 0010 0100 1 .. ... ... .. 1 1000 0001 75 1023 3201 6 0010 0100 1 .. ... ... .. 1 1000 0001 79 1033 3301 7 0010 0100 1 .. ... ... .. 1 1000 0001 138 2022 2202 6 0100 0010 . 1. ... ... .1 . 1000 0001 139 2023 3202 7 0100 0010 . 1. ... ... .1 . 1000 0001 143 2033 3302 8 0100 0010 . 1. ... ... .1 . 1000 0001 154 2122 2212 7 0100 0010 . .1 ... ... 1. . 0100 0010 155 2123 3212 8 0100 0010 . .1 ... ... 1. . 0100 0010 159 2133 3312 9 0100 0010 . .1 ... ... 1. . 0100 0010 207 3033 3303 9 1000 0001 . .. 1.. ..1 .. . 1000 0001 223 3133 3313 10 1000 0001 . .. .1. .1. .. . 0100 0010 239 3233 3323 11 1000 0001 . .. ..1 1.. .. . 0010 0100

5 sequences with inversion set 5

These 5 sequences have the place-based inversion set of permutation ${\mathit {5}}$ in common, i.e. $\{(0,1),(0,2),(1,2)\}$ or . Thus l = (0, 1, 2, 0) and r = (2, 1, 0, 0). 0 1 2 3 4 S # u e-b v 146 2102 2012 5 0210 0120 1 11 ... ... 11 1 2100 0012 147 2103 3012 6 0210 0120 1 11 ... ... 11 1 2100 0012 211 3103 3013 7 2010 0102 1 .. 11. .11 .. 1 2100 0012 227 3203 3023 8 2100 0012 . 1. 1.1 1.1 .1 . 2010 0102 231 3213 3123 9 2100 0012 . .1 .11 11. 1. . 0210 0120