

A180632


Minimum length of a word on n letters that contains every permutation (lengthn word on distinct letters).


4




OFFSET

0,3


COMMENTS

Obviously bounded below by n!+n1 and above by 2(n!(n1)!)+1.
A better lower bound is n! + (n1)! + (n2)! + n3 and a better upper bound is A007489(n).
Was conjectured equal to A007489, but now known that a(n) < A007489(n) for all n > 5.  Robin Houston, Aug 22 2014


REFERENCES

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


LINKS

Table of n, a(n) for n=0..5.
J. A. Barnett, Permutation Strings
Robin Houston, Tackling the Minimal Superpermutation Problem, arXiv:1408.5108, 2014.
Nathaniel Johnston, Nonuniqueness of minimal superpermutations, Discrete Math., 313 (2013), 15531557.
Nathaniel Johnston, The minimal superpermutation problem, 2013.
Nathaniel Johnston, All minimal superpermutations on five symbols have been found


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.


CROSSREFS

Cf. A188428, A224986.
Sequence in context: A049425 A012584 A101899 * A009220 A007489 A201968
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


STATUS

approved



