A188428 -id:A188428 - 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

A224986 a(n) = Product_{k=1..n-4} (n-k-2)!^(k*k!).

Original entry on oeis.org

1, 1, 1, 1, 2, 96, 8153726976, 320352637207127391364950814323398779319161580421120

Offset: 1

Nathaniel Johnston, Apr 22 2013

Consider words on n symbols that contain every permutation of those n symbols as contiguous substrings. The minimal length of such a string was conjectured to equal A007489(n) (see A180632). This sequence is a lower bound on the number of distinct (up to relabeling the symbols) such strings of the conjectured minimal length.
It was conjectured in the Ashlock paper that, for all n, there is only one string of length A007489(n) containing all permutations. This sequence shows that this conjecture fails as n grows.
In 2014 Houston has shown that the first conjecture about the minimal length is also false for all n > 5. In particular, A180632(6) <= 872 = A007489(n). - M. F. Hasler, Jul 28 2020
The next term a(9) ~ 2.18e291 is too large to be displayed here. - M. F. Hasler, Jul 29 2020

			a(n) = 1 for n <= 4, which agrees with the fact that the minimal strings containing all permutations in these cases are unique (see A180632).

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

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.
Nathaniel Johnston, The Minimal Superpermutation Problem, 2013.

Cf. A180632, A188428.

seq(product((n-k-2)!^(k*k!),k=1..max(n-4,0)),n=1..8);

apply( {A224986(n)=prod(k=1,n-4,(n-k-2)!^(k*k!))}, [1..8]) \\ M. F. Hasler, Jul 29 2020

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