A332089 -id:A332089 - cp's OEIS frontend

A180632 Minimum length of a string over the alphabet A = {1,2,...,n} that contains every permutation of A as a substring exactly once, also known as length of the minimal super-permutation.

0, 1, 3, 9, 33, 153

Offset: 0

Michael Hamm, Sep 13 2010

Obviously bounded below by n! + n - 1 and above by 2(n! - (n - 1)!) + 1.
A better lower bound is n! + (n - 1)! + (n - 2)! + n - 3 (A376269) and a better upper bound is A007489(n). - Nathaniel Johnston, Apr 22 2013
The above mentioned lower bound was essentially shown in 2011 by an anonymous poster on the internet and, filling in some minor details, brought into a formal form by Houston, Pantone and Vatter (see reference). - Peter Luschny, Oct 27 2018
Was conjectured to be equal to A007489, but it is now known that a(n) < A007489(n) for all n > 5. - Robin Houston, Aug 22 2014
Different from the minimal supersequence, in which each permutations of n letters can appear as a subsequence instead of a sub-string (i.e., with noncontiguous characters). Refer to A062714. - Maurizio De Leo, Mar 02 2015
In October 2018 Greg Egan found new records for n=7, 8, 9: a(7) <= 5908, a(8) <= 46205, and a(9) <= 408966. More generally, for any n >= 7, a(n) <= n! + (n-1)! + (n-2)! + (n-3)! + n - 3. - Peter Luschny, Oct 26 2018; corrected by Max Alekseyev, Jan 07 2019
In February 2019, Bogdan Coanda found an example showing that a(7) <= 5907. Later the same month, Greg Egan found an example showing a(7) <= 5906. - Robin Houston, Mar 11 2019
a(6) <= 872 = A007489(6) - 1 [Houston 2014]. - M. F. Hasler, Jul 28 2020

			For n = 1, 2, 3, 4, the (unique, up to relabeling the symbols) minimal words are:
1
121
123121321
123412314231243121342132413214321
For n = 5, there are exactly 8 distinct (up to relabeling the symbols) minimal words.
Comment from _N. J. A. Sloane_, Mar 27 2015: From the Houston (2014 arXiv) paper, a superpermutation of length 872 (not known to be minimal, but shorter than the old upper bound of 873):
  1234561234516234512634512364513264513624513642513645213645123465123415 6234152634152364152346152341652341256341253641253461253416253412653412 3564123546123541623541263541236541326543126453162435162431562431652431 6254316245316425314625314265314256314253614253164523146523145623145263 1452361452316453216453126435126431526431256432156423154623154263154236 1542316542315642135642153624153621453621543621534621354621345621346521 3462513462153642156342165342163542163452163425163421564325164325614325 6413256431265432165432615342613542613452613425613426513426153246513246 5312463512463152463125463215463251463254163254613254631245632145632415 6324516324561324563124653214653241653246153264153261453261543265143625 1436521435621435261435216435214635214365124361524361254361245361243561 2436514235614235164235146235142635142365143265413625413652413562413526 41352461352416352413654213654123

D. Ashlock and J. Tillotson. Construction of small superpermutations and minimal injective superstrings. Congressus Numerantium, 93 (1993), 91-98.

Dhruv Ajmera, An O(n) Space Construction of Superpermutations, arXiv:2505.09628 [cs.DM], 2025. See p. 29.
Anonymous 4chan Poster, Robin Houston, Jay Pantone and Vince Vatter, A lower bound on the length of the shortest superpattern, October 25, 2018.
Jeffrey A. Barnett, Permutation Strings
Greg Egan, Superpermutations, October 20, 2018.
Michael Engen and Vincent Vatter, Containing all permutations, Amer. Math. Monthly, 128 (2021), 4-24, section 2; arXiv preprint, arXiv:1810.08252 [math.CO], 2018-2020.
James Grime and Brady Haran, Superpermutations, Numberphile video, 2018.
James Grime, Matt Parker and Robin Houston, New Superpermutations Discovered!, standupmaths video, March 11, 2019.
Robin Houston, Tackling the Minimal Superpermutation Problem, arXiv:1408.5108 [math.CO], 2014.
Robin Houston and Matt Parker, Superpermutations: the maths problem solved by 4chan, standupmaths video (2019).
Nathaniel Johnston, Non-uniqueness of minimal superpermutations, Discrete Math., 313 (2013), 1553-1557.
Nathaniel Johnston, The minimal superpermutation problem, 2013.
Nathaniel Johnston, All minimal superpermutations on five symbols have been found
Miryana Stefanović, Supermutacije (Supermutations), Master's Thesis, Univ. Belgrade (Serbia 2023). See p. 9. (In Serbian)
Wikipedia, Superpermutation
Aaron Williams, Hamiltonicity of the Cayley digraph on the symmetric group generated by sigma = (1 2 ... n) and tau = (1 2), arXiv:1307.2549v3 [math.CO], 2017.

Cf. A188428, A224986, A062714, A007489, A376269.

Row lengths of A332089 (for n >= 1).

Edited and expanded by Nathaniel Johnston, Apr 22 2013
a(5) computed by Benjamin Chaffin and verified by Nathaniel Johnston, Aug 13 2014
Definition edited by Maurizio De Leo, Mar 02 2015; and by Max Alekseyev, Jan 07 2019

A376269 a(n) = n! + (n - 1)! + (n - 2)! + n - 3.

Original entry on oeis.org

3, 9, 33, 152, 867, 5884, 46085, 408246, 4032007, 43908488, 522547209, 6745939210, 93884313611, 1401079680012, 22317642547213, 377917892352014, 6778983923712015, 128403161542656016, 2560949482291200017, 53645489280294912018, 1177524571957493760019, 27027108408834293760020

Offset: 2

Paolo Xausa, Sep 18 2024

a(n) is a lower bound for the length of every superpermutation on n symbols (see links). An upper bound for the length of a minimal superpermutation is given by A341300(n).

Paolo Xausa, Table of n, a(n) for n = 2..400
Anonymous 4chan poster, Robin Houston, Jay Pantone, and Vince Vatter, A lower bound on the length of the shortest superpattern, 2018.
Michael Engen and Vincent Vatter, Containing All Permutations, The American Mathematical Monthly, 128 (1), 2021, pp. 4-24 (preprint version).
James Grime and Brady Haran, Superpermutations, Numberphile video, 2018.
Wikipedia, Superpermutation.

Cf. A054119, A180632, A332089, A341300.

Table[n^2 * (n - 2)! + n - 3, {n, 2, 25}]

from sympy import factorial
def A376269(n): return n**2*factorial(n-2)+n-3 # Chai Wah Wu, Sep 20 2024

a(n) = A054119(n) + n - 3.
E.g.f.: (3 - x - x^2 - exp(x)*(3 - 4*x + x^2) - (1 - x)*x*log(1 - x))/(1 - x). - Stefano Spezia, Sep 18 2024
a(n) = (n-2)!*n^2 + n - 3. - Chai Wah Wu, Sep 20 2024
D-finite with recurrence (-n+1)*a(n) +(n-2)*(n+2)*a(n-1) -(n-1)*(n-3)*a(n-2) -(4*n-7)*(n-4)=0. - R. J. Mathar, Sep 23 2024

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

Original entry on oeis.org

1, 16, 112249, 36192508500267905991836

Offset: 1

M. F. Hasler, Jul 28 2020

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.

			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.

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.

Cf. A180632, A007489.

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)

A341300 a(n) = n! + (n-1)! + (n-2)! + (n-3)! + n - 3.

Original entry on oeis.org

10, 34, 154, 873, 5908, 46205, 408966, 4037047, 43948808, 522910089, 6749568010, 93924230411, 1401558681612, 22323869568013, 378005070643214, 6780291598080015, 128424084332544016, 2561305169719296017, 53651891654000640018, 1177646217057902592019

Offset: 3

N. J. A. Sloane, Feb 13 2021

nonn

a(n) is an upper bound for the length of a minimal superpermutation on n symbols (see links). A lower bound is given by A376269(n). - Paolo Xausa, Sep 27 2024

Michael De Vlieger, Table of n, a(n) for n = 3..449
Michael Engen and Vincent Vatter, Containing all permutations, Amer. Math. Monthly, 128 (2021), 4-24; arXiv preprint, arXiv:1810.08252 [math.CO], 2018-2020.
Wikipedia, Superpermutation.

Cf. A180632, A332089, A376269.

Array[Total[(# - Range[0, 3])!] + # - 3 &, 20, 3] (* Michael De Vlieger, Apr 07 2021 *)

from sympy import factorial
def A341300(n): return (n**2*(n-2)+1)*factorial(n-3)+n-3 # Chai Wah Wu, Sep 20 2024

a(n) = (n-3)!*(n^2*(n-2) + 1) + n - 3. - Chai Wah Wu, Sep 20 2024

A376069 a(n) is the lexicographically earliest minimal superpermutation on n symbols, where the symbols are {1, 2, ..., n}, with 1 <= n <= 9.

Original entry on oeis.org

1, 121, 123121321, 123412314231243121342132413214321, 123451234152341253412354123145213425134215342135421345214352145321452314253142351423154231245312435124315243125432154325143254132451324153241352413254312

Offset: 1

Paolo Xausa, Sep 20 2024

Please refer to A332089 (the main entry, where symbols in each superpermutation are individually listed) for more information.

In this sequence superpermutations are encoded by concatenating the symbols in a single word. Such encoding ensures unambiguous representation only up to n = 9.

Michael Engen and Vincent Vatter, Containing All Permutations, The American Mathematical Monthly, 128 (1), 2021, pp. 4-24 (preprint version).
James Grime and Brady Haran, Superpermutations, Numberphile video, 2018.
Nathaniel Johnston, Non-uniqueness of minimal superpermutations, Discrete Mathematics, Vol. 313, Issue 14, 2013, pp. 1553-1557 (preprint version).
Nathaniel Johnston, All Minimal Superpermutations on Five Symbols Have Been Found, 2014.
Wikipedia, Superpermutation.

Cf. A180632, A332089, A332090, A341300, A376269.

A376572 Triangle read by rows: T(n,k) is the frequency of the symbol k in the lexicographically earliest minimal superpermutation on n symbols, where the symbols are {1, 2, ..., n}.

Original entry on oeis.org

1, 2, 1, 4, 3, 2, 10, 9, 8, 6, 32, 33, 31, 31, 26

Offset: 1

Paolo Xausa, Sep 28 2024

Equivalently, T(n,k) is the frequency of k in row n of A332089 (see there for more information).

			Triangle begins:
  n\k|  1   2   3   4   5  ...
  ----------------------------
   1 |  1;
   2 |  2,  1;
   3 |  4,  3,  2;
   4 | 10,  9,  8,  6;
   5 | 32, 33, 31, 31, 26;
  ...
For n = 3, the minimal superpermutation is 123121321; symbol 1 appears 4 times, symbol 2 appears 3 times and symbol 3 appears 2 times.

Michael Engen and Vincent Vatter, Containing All Permutations, The American Mathematical Monthly, 128 (1), 2021, pp. 4-24 (preprint version).
Wikipedia, Superpermutation.

Cf. A180632 (row sums, for n >= 1), A332089.

cp's OEIS Frontend

A180632 Minimum length of a string over the alphabet A = {1,2,...,n} that contains every permutation of A as a substring exactly once, also known as length of the minimal super-permutation.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A376269 a(n) = n! + (n - 1)! + (n - 2)! + n - 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A341300 a(n) = n! + (n-1)! + (n-2)! + (n-3)! + n - 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

A376069 a(n) is the lexicographically earliest minimal superpermutation on n symbols, where the symbols are {1, 2, ..., n}, with 1 <= n <= 9.

Views

Author

Keywords

Comments

Links

Crossrefs

A376572 Triangle read by rows: T(n,k) is the frequency of the symbol k in the lexicographically earliest minimal superpermutation on n symbols, where the symbols are {1, 2, ..., n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs