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,3

Comments

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 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

References

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

Links

Table of n, a(n) for n=0..5.

Anonymous 4chan Poster, Robin Houston, Jay Pantone and Vince Vatter, A lower bound on the length of the shortest superpattern, October 25, 2018.

J. A. Barnett, Permutation Strings

Greg Egan, Superpermutations, October 20, 2018.

M. Engen and V. 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.

Example

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

Crossrefs

Cf. A188428, A224986, A062714, A007489.

Sequence in context: A277395 A012584 A101899 * A279840 A009220 A294035

Adjacent sequences: A180629 A180630 A180631 * A180633 A180634 A180635

Keyword

nonn,hard,more

Author

Michael Hamm, Sep 13 2010

Extensions

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

Status

approved