View source for Inversions in sequences

{| align="right" style="text-align:right; border:1px solid lightgray" cellspacing="10"
| [[Inversion (discrete mathematics)]] {{rdrup}}
|}

This page shows the 4<sup>4</sup> = 256 sequences of length 4 with possible entries from 0...3. These are the integers 0...255 in [[w:Quaternary numeral system|base 4]].

It shows their place-based and element based inversion sets, and all four possible vectors related to them.<br>
{{invvect|l}} and {{invvect|r}} are the left and right inversion counts, and {{invvect|v}} is the inversion vector. The fourth possible vector is unused, but added as {{invvect|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.<br>
There are 35 sequences with the inversion set of permutation <math>\mathit{0}</math>, while that of <math>\mathit{23}</math> is unique.<br>
The inversion sets of the permutations <math>\mathit{1}</math>, <math>\mathit{2}</math>, <math>\mathit{3}</math>, <math>\mathit{4}</math>, <math>\mathit{6}</math>, <math>\mathit{8}</math>, <math>\mathit{9}</math>, <math>\mathit{12}</math>, <math>\mathit{13}</math>, <math>\mathit{16}</math> and <math>\mathit{18}</math> appear 15 times each, while those of <math>\mathit{5}</math>, <math>\mathit{7}</math>, <math>\mathit{10}</math>, <math>\mathit{11}</math>, <math>\mathit{14}</math>, <math>\mathit{15}</math>, <math>\mathit{17}</math>, <math>\mathit{19}</math>, <math>\mathit{20}</math>, <math>\mathit{21}</math> and <math>\mathit{22}</math> appear 5 times each.

The element-based inversion sets are [[w:Multiset|multisets]], as different pairs of places can have the same pair of elements.<br>
There are 103 different multisets, corresponding to 40 different inversion vectors {{invvect|v}}.<br>
So there are 40 − 24 = 16 inversion vectors that permutations can not have — e.g. (4, 0, 0<span style="opacity: .3;">, 0</span>), (0, 3, 0<span style="opacity: .3;">, 0</span>) and (0, 0, 2<span style="opacity: .3;">, 0</span>).

==Permutations==

{| class="collapsible collapsed" style="width: 100%; border: 1px solid #aaa; border-bottom:0;"
!bgcolor="#f2f2f2"| 24 permutations of 0 1 2 3
|-
|bgcolor="white"|
[[File:4-el perm invmap 16.svg|thumb]]
This list is like [[Inversion_(discrete_mathematics)#Example:_All_permutations_of_four_elements|the one]] in the inversion article, but more detailed.

'''S'''<sub>rev colex</sub> = {{invvect|l}}<sub>colex</sub> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
'''S'''<sub>lex</sub> = {{invvect|r}}<sub>lex</sub><br>
{{invvect|u}}<sub>colex</sub> = inverses of '''S'''<sub>rev colex</sub> = {{oeis|A056019}}(0..23) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
{{invvect|v}}<sub>lex</sub> = inverses of '''S'''<sub>lex</sub>

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.<br>
'''p-b'''<sub>lex</sub> = {{invvect|l}}<sub>lex</sub> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
'''e-b'''<sub>lex</sub> = {{invvect|u}}<sub>lex</sub> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
'''p-b'''<sub>colex</sub> = (0, 1, 3, 2, 4, 5, 9...) = {{oeis|A211363}}(0..23)

The unlabelled columns on the right bring the permutations in the orders generated by [[w:Heap's algorithm|Heap's]] and [[w:Steinhaus–Johnson–Trotter algorithm|Steinhaus–Johnson–Trotter algorithm]].<br>
The former is (0, 1, 3, 2, 4, 5, 11...) = {{oeis|A280318}}(0..23). The latter is (0, 6, 8, 9, 15, 14, 12...) = {{oeis|A280319}}(4, 0..23).

{{4-el sequence inversions; permutations}}
|}

{| class="collapsible collapsed" style="width: 100%; border: 1px solid #aaa; border-bottom:0;"
!bgcolor="#f2f2f2"| 12 permutations of 0 0 1 3
|-
|bgcolor="white"|
[[File:4-el sequence invmap 1300.svg|thumb]]
These are essentially the the 12 permutations of 1 1 2 4 [[w:Narayana Pandit|Narayana]] has listed in reverse colex order in [[w:Ganita Kaumudi|''Ganita Kaumudi'']], as mentioned by [[w:Donald Knuth|Knuth]] in volume 4 of [[w:TAoCP|TAoCP]].

<small>{{cite book
 | last = Knuth | first = Donald
 | title = The art of computer programming
 | chapter = 7.2.1.7 History and further references
 | publisher = Addison-Wesley | year = 2005 | isbn = 0321335708 }}
— ''The work of Narayana'' (p. 62)</small>

<small>Singh, Parmanand (1998): "[http://sandhi.hss.iitb.ac.in/index.php/articles-new/science-and-technology/mathematics/1914-ganitakaumudi-of-narayana-tr-parmanand-singh The Ganita Kaumudi of Narayana Pandita]"
— ''Expansion (i.e., Serial Arrangement of Permutations)'' (p. 47)</small>

{{Template:4-el sequence inversions; permutations of 0013}}
|}

{| class="collapsible collapsed" style="width: 100%; border: 1px solid #aaa;"
!bgcolor="#f2f2f2"| 6 permutations of 0 0 1 1
|-
|bgcolor="white"|
[[File:4-el sequence invmap 1100.svg|thumb]]
{{Template:4-el sequence inversions; permutations of 0011}}
|}

==Place based inversion sets==

{| class="collapsible collapsed" style="width: 100%; border: 1px solid #aaa; border-bottom:0;"
!bgcolor="#f2f2f2"| 15 sequences with inversion set 1
|-
|bgcolor="white"|
These 15 sequences have the place-based inversion set of permutation <math>\mathit{1}</math> in common, i.e. <math>\{(0,1)\}</math> or [[File:4-el perm invset 01.svg|55px]].<br>
Thus {{invvect|l}} = (<span style="opacity: .3;">0, </span>1, 0, 0) and {{invvect|r}} = (1, 0, 0<span style="opacity: .3;">, 0</span>).

{{4-el sequence inversions; invset 1}}
|}

{| class="collapsible collapsed" style="width: 100%; border: 1px solid #aaa;"
!bgcolor="#f2f2f2"| 5 sequences with inversion set 5
|-
|bgcolor="white"|

These 5 sequences have the place-based inversion set of permutation <math>\mathit{5}</math> in common, i.e. <math>\{(0,1), (0,2), (1,2)\}</math> or [[File:4-el perm invset 05.svg|55px]].<br>
Thus {{invvect|l}} = (<span style="opacity: .3;">0, </span>1, 2, 0) and {{invvect|r}} = (2, 1, 0<span style="opacity: .3;">, 0</span>).

{{4-el sequence inversions; invset 5}}
|}









[[Category:Inversion (discrete mathematics)]]