login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 11

%I #123 Feb 02 2024 09:06:53

%S 0,1,3,9,33,153

%N 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.

%C Obviously bounded below by n! + n - 1 and above by 2(n! - (n - 1)!) + 1.

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

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

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

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

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

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

%C a(6) <= 872 = A007489(6) - 1 [Houston 2014]. - _M. F. Hasler_, Jul 28 2020

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

%H Anonymous 4chan Poster, Robin Houston, Jay Pantone and Vince Vatter, <a href="/A180632/a180632.pdf">A lower bound on the length of the shortest superpattern</a>, October 25, 2018.

%H J. A. Barnett, <a href="http://www.notatt.com/permutations.pdf">Permutation Strings</a>

%H Greg Egan, <a href="http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html">Superpermutations</a>, October 20, 2018.

%H M. Engen and V. Vatter. <a href="https://doi.org/10.1080/00029890.2021.1835384">Containing all permutations</a>, Amer. Math. Monthly, 128 (2021), 4-24, section 2; <a href="https://arxiv.org/abs/1810.08252">arXiv preprint</a>, arXiv:1810.08252 [math.CO], 2018-2020.

%H James Grime and Brady Haran, <a href="https://www.youtube.com/embed/wJGE4aEWc28?end=476">Superpermutations</a>, Numberphile video, 2018.

%H James Grime, Matt Parker and Robin Houston, <a href="https://www.youtube.com/watch?v=_tpNuulTeSQ">New Superpermutations Discovered!</a>, standupmaths video, March 11, 2019.

%H Robin Houston, <a href="http://arxiv.org/abs/1408.5108">Tackling the Minimal Superpermutation Problem</a>, arXiv:1408.5108 [math.CO], 2014.

%H Robin Houston and Matt Parker, <a href="https://www.youtube.com/watch?v=OZzIvl1tbPo">Superpermutations: the maths problem solved by 4chan</a>, standupmaths video (2019).

%H Nathaniel Johnston, <a href="http://arxiv.org/abs/1303.4150">Non-uniqueness of minimal superpermutations</a>, Discrete Math., 313 (2013), 1553-1557.

%H Nathaniel Johnston, <a href="http://www.njohnston.ca/2013/04/the-minimal-superpermutation-problem/">The minimal superpermutation problem</a>, 2013.

%H Nathaniel Johnston, <a href="http://www.njohnston.ca/2014/08/all-minimal-superpermutations-on-five-symbols-have-been-found/">All minimal superpermutations on five symbols have been found</a>

%H Miryana Stefanović, <a href="http://elibrary.matf.bg.ac.rs/bitstream/handle/123456789/5627/v1_masterMirjanaStefanovic.pdf">Supermutacije</a> (Supermutations), Master's Thesis, Univ. Belgrade (Serbia 2023). See p. 9. (In Serbian)

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Superpermutation">Superpermutation</a>

%H Aaron Williams, <a href="http://arxiv.org/abs/1307.2549">Hamiltonicity of the Cayley digraph on the symmetric group generated by sigma = (1 2 ... n) and tau = (1 2)</a>, arXiv:1307.2549v3 [math.CO], 2017.

%e For n = 1, 2, 3, 4, the (unique, up to relabeling the symbols) minimal words are:

%e 1

%e 121

%e 123121321

%e 123412314231243121342132413214321

%e For n = 5, there are exactly 8 distinct (up to relabeling the symbols) minimal words.

%e 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):

%e 1234561234516234512634512364513264513624513642513645213645123465123415 6234152634152364152346152341652341256341253641253461253416253412653412 3564123546123541623541263541236541326543126453162435162431562431652431 6254316245316425314625314265314256314253614253164523146523145623145263 1452361452316453216453126435126431526431256432156423154623154263154236 1542316542315642135642153624153621453621543621534621354621345621346521 3462513462153642156342165342163542163452163425163421564325164325614325 6413256431265432165432615342613542613452613425613426513426153246513246 5312463512463152463125463215463251463254163254613254631245632145632415 6324516324561324563124653214653241653246153264153261453261543265143625 1436521435621435261435216435214635214365124361524361254361245361243561 2436514235614235164235146235142635142365143265413625413652413562413526 41352461352416352413654213654123

%Y Cf. A188428, A224986, A062714, A007489.

%K nonn,hard,more

%O 0,3

%A _Michael Hamm_, Sep 13 2010

%E Edited and expanded by _Nathaniel Johnston_, Apr 22 2013

%E a(5) computed by _Benjamin Chaffin_ and verified by _Nathaniel Johnston_, Aug 13 2014

%E Definition edited by _Maurizio De Leo_, Mar 02 2015; and by _Max Alekseyev_, Jan 07 2019

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 10:55 EDT 2024. Contains 371241 sequences. (Running on oeis4.)