1,3

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.

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

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.

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.

(PARI) A332089_row(n)=digits(A332090(n), n+1)

(PARI) /* 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))}

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

Adjacent sequences: A332086 A332087 A332088 * A332090 A332091 A332092

nonn,hard,tabf

M. F. Hasler, Jul 31 2020

approved