login
A332089
Irregular table read by rows, where row n lists the lexicographically first superpermutation of minimal length over {1, ..., n}.
6
1, 1, 2, 1, 1, 2, 3, 1, 2, 1, 3, 2, 1, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 1, 2, 5, 3, 4, 1, 2, 3, 5, 4, 1, 2, 3, 1, 4, 5, 2, 1, 3, 4, 2, 5, 1, 3, 4, 2, 1, 5, 3, 4, 2, 1, 3, 5, 4, 2, 1, 3, 4, 5, 2, 1, 4, 3, 5, 2, 1, 4, 5, 3, 2, 1, 4, 5, 2, 3, 1, 4, 2, 5
OFFSET
1,3
COMMENTS
Sequence A180632 gives the row lengths and more information about superpermutations, i.e., strings over a finite alphabet that contain all permutations thereof as a substring.
In March 2014, Ben Chaffin showed that minimal superpermutations of order n = 5 have length 153, and found all 8 distinct superpermutations of this kind; the (non-palindromic) lexicographically first one is row 5 of this table. For n = 6, Robin Houston has found a few months later several superpermutations of length 872 (one less than the previously conjectured minimal length), but we still don't know which is the shortest (and/or lexico-first) superpermutation for that case.
LINKS
Robin Houston, Tackling the Minimal Superpermutation Problem, arXiv:1408.5108 [math.CO], 2014.
Nathaniel Johnston, Non-uniqueness of minimal superpermutations, arXiv:1303.4150 [math.CO], 2013; Discrete Math., 313 (2013), 1553-1557.
Wikipedia, Superpermutation
FORMULA
For n < 5, row n results from row n - 1 by making the list of all substrings which are permutations, duplicating them and inserting (n) between the two copies, and merging them together again, with overlap reduced as much as possible.
EXAMPLE
The table starts:
n | SP[n]
----+---------------------------
1 | (1)
2 | (1, 2, 1)
3 | (1, 2, 3, 1, 2, 1, 3, 2, 1)
4 | (1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 3, 1, 2, 4, 3, 1, 2,
| 1, 3, 4, 2, 1, 3, 2, 4, 1, 3, 2, 1, 4, 3, 2, 1)
5 | (1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 1, 2, 5, 3, 4, 1,
| 2, 3, 5, 4, 1, 2, 3, 1, 4, 5, 2, 1, 3, 4, 2, 5, 1, 3, 4,
| 2, 1, 5, 3, 4, 2, 1, 3, 5, 4, 2, 1, 3, 4, 5, 2, 1, 4, 3,
| 5, 2, 1, 4, 5, 3, 2, 1, 4, 5, 2, 3, 1, 4, 2, 5, 3, 1, 4,
| 2, 3, 5, 1, 4, 2, 3, 1, 5, 4, 2, 3, 1, 2, 4, 5, 3, 1, 2,
| 4, 3, 5, 1, 2, 4, 3, 1, 5, 2, 4, 3, 1, 2, 5, 4, 3, 2, 1,
| 5, 4, 3, 2, 5, 1, 4, 3, 2, 5, 4, 1, 3, 2, 4, 5, 1, 3, 2,
| 4, 1, 5, 3, 2, 4, 1, 3, 5, 2, 4, 1, 3, 2, 5, 4, 3, 1, 2)
One can consider an initial row 0 of length 0, producing row 1 as concatenation of (), (1), ().
Row 2 results from duplicating row 1 with (2) inserted in the middle.
Row 3 results from making the list of all permutations in row 2, ((1, 2), (2, 1)), then duplicating these and inserting (3), i.e.: ((1, 2, 3, 1, 2), (2, 1, 3, 2, 1)), then merging together with the second instance of the overlapping '2' removed in the middle.
Row 4 results in the same way from row 3, where the permutations are all length 3 substrings except for the middle (1, 2, 1).
Applying the same procedure to row 4 yields a superpermutation of {1, ..., 5} of minimal length 153 which is palindromic as the earlier ones, but not the lexicographically first one, which is given above.
PROG
(PARI) A332089_row(n)=digits(A332090(n), n+1) /* or, independent of A332090: */
A332089_row(n)={n>5 && error("not yet implemented"); digits(fromdigits([d-37| d<-Vecsmall(["&", "&:", "&<12:", "&<N<3<1P12O2=2:P:", "&<R1G4<N>G1HN<3Y2OXG" ":ZO2[:GY3H:RE3YDOZ3<XOD[<1RD=H1P4=D>P:[EXP>NER2=4ENH=2>P1"][n])], 100))}
CROSSREFS
Cf. A180632 (row lengths = minimal size of order n superpermutations), A332090 (row n read as base-(n+1) number).
Sequence in context: A284271 A241915 A301891 * A177219 A277700 A140191
KEYWORD
nonn,hard,tabf
AUTHOR
M. F. Hasler, Jul 31 2020
STATUS
approved