cp's OEIS Frontend

A332089 Irregular table read by rows, where row n lists the lexicographically first superpermutation of minimal length over {1, ..., n}.

%I A332089 #25 May 23 2025 18:23:14
%S A332089 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,
%T A332089 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,
%U A332089 1,4,3,5,2,1,4,5,3,2,1,4,5,2,3,1,4,2,5
%N A332089 Irregular table read by rows, where row n lists the lexicographically first superpermutation of minimal length over {1, ..., n}.
%C A332089 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.
%C A332089 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.
%H A332089 Robin Houston, <a href="http://arxiv.org/abs/1408.5108">Tackling the Minimal Superpermutation Problem</a>, arXiv:1408.5108 [math.CO], 2014.
%H A332089 Nathaniel Johnston, <a href="http://arxiv.org/abs/1303.4150">Non-uniqueness of minimal superpermutations</a>, arXiv:1303.4150 [math.CO], 2013; Discrete Math., 313 (2013), 1553-1557.
%H A332089 Wikipedia, <a href="http://en.wikipedia.org/wiki/Superpermutation">Superpermutation</a>
%F A332089 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.
%e A332089 The table starts:
%e A332089   n | SP[n]
%e A332089 ----+---------------------------
%e A332089   1 | (1)
%e A332089   2 | (1, 2, 1)
%e A332089   3 | (1, 2, 3, 1, 2, 1, 3, 2, 1)
%e A332089   4 | (1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 3, 1, 2, 4, 3, 1, 2,
%e A332089     |     1, 3, 4, 2, 1, 3, 2, 4, 1, 3, 2, 1, 4, 3, 2, 1)
%e A332089   5 | (1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 1, 2, 5, 3, 4, 1,
%e A332089     |     2, 3, 5, 4, 1, 2, 3, 1, 4, 5, 2, 1, 3, 4, 2, 5, 1, 3, 4,
%e A332089     |     2, 1, 5, 3, 4, 2, 1, 3, 5, 4, 2, 1, 3, 4, 5, 2, 1, 4, 3,
%e A332089     |     5, 2, 1, 4, 5, 3, 2, 1, 4, 5, 2, 3, 1, 4, 2, 5, 3, 1, 4,
%e A332089     |     2, 3, 5, 1, 4, 2, 3, 1, 5, 4, 2, 3, 1, 2, 4, 5, 3, 1, 2,
%e A332089     |     4, 3, 5, 1, 2, 4, 3, 1, 5, 2, 4, 3, 1, 2, 5, 4, 3, 2, 1,
%e A332089     |     5, 4, 3, 2, 5, 1, 4, 3, 2, 5, 4, 1, 3, 2, 4, 5, 1, 3, 2,
%e A332089     |     4, 1, 5, 3, 2, 4, 1, 3, 5, 2, 4, 1, 3, 2, 5, 4, 3, 1, 2)
%e A332089 One can consider an initial row 0 of length 0, producing row 1 as concatenation of (), (1), ().
%e A332089 Row 2 results from duplicating row 1 with (2) inserted in the middle.
%e A332089 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.
%e A332089 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).
%e A332089 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.
%o A332089 (PARI) A332089_row(n)=digits(A332090(n),n+1)
%o A332089 (PARI) /* Independent of A332090: */
%o A332089 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))}
%Y A332089 Cf. A180632 (row lengths = minimal size of order n superpermutations), A332090 (row n read as base-(n+1) number).
%K A332089 nonn,hard,tabf
%O A332089 1,3
%A A332089 _M. F. Hasler_, Jul 31 2020