A332090 The smallest superpermutation of order n, read as a base n+1 number.

1, 16, 112249, 36192508500267905991836

Offset: 1

Author

M. F. Hasler, Jul 28 2020

Keywords

• nonn
• base

Comments

A superpermutation of order n is a string over the alphabet {1,...,n} such that every permutation of {1,...,n} occurs as a substring.

Such a string is the base n+1 representation of some number. The terms a(n) here are these numbers, corresponding to the lexicographically first superpermutation of minimal length A180632(n). This is the meaning of "smallest" in the name.

It is known that the superpermutations of minimal length are unique only for n < 5. For n = 5 there are 8 inequivalent superpermutations of minimal length 153. The lexicographically first one would correspond to

a(5) = 27360223915482678295044186051702391878951111088124776744577\

815578589162223809195375150272260250093757648411736389359241,

while there is a unique palindromic one corresponding to a larger term, produced by the standard algorithm given in A332089's formula section.

The smallest superpermutation for n = 6 is not yet known for sure. The smallest known has 872 letters, so a(6) ~ 7^870 ~ 10^735, which is too large to be displayed here.

Examples

			For n=2, the shortest superpermutation is '121': it contains the permutations (1,2) and (2,1) as substrings. Considered as a number in base 3 this is 1*3^2 + 2*3 + 1 = 16 = a(2).
For n=3, the shortest superpermutation is '123121321': it contains all permutations of {1,2,3} as substrings. As a number written in base 4 this is 1*4^8 + 2*4^7 + ... + 1 = 112249 = a(3).
For n=4, the shortest superpermutation is '123412314231243121342132413214321'. As a number written in base 5 this is 1*5^32 + ... + 2*5 + 1 = 36192508500267905991836 = a(4).
From n=5 on, the shortest superpermutation is no longer unique: there are 8 inequivalent ones of minimal length 153. Only one of them is symmetric with respect to reversal of the digits, which is not the case for the lexicographically first one, which corresponds to the number a(5) ~ 6^152 + 2*6^151 + ... + 1*6 + 2 ~ 2.7e18.
		

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.

Crossrefs

Cf. A180632, A007489.

Programs

PARI

SP=[1, 121, 123121321, 123412314231243121342132413214321, fromdigits([d-37| d<-Vecsmall("&G1HN<3Y2OXG:ZO2[:GY3H:RE3YDOZ3P:[EXP>NER2=4ENH=2>P1")], 100)] \\ custom base100 encoding
  A332090(n)=fromdigits(digits(SP[n]),n+1)
/* Alternatively, considering A332089 as the more fundamental sequence: */
A332090(n)=fromdigits(A332089_row(n),n+1)