

A180632


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


3




OFFSET

0,3


COMMENTS

a(4)=33, larger values unknown as of time of submission, but suspected possibly equal to A007489.
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).


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..4.
J. A. Barnett, Permutation Strings
Nathaniel Johnston, Nonuniqueness of minimal superpermutations, Discrete Math., 313 (2013), 15531557.
Nathaniel Johnston, The Minimal Superpermutation Problem, 2013.


EXAMPLE

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


CROSSREFS

Cf. A188428, A224986.
Sequence in context: A210689 A009356 A058138 * A219557 A094538 A037129
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


STATUS

approved



