

A180632


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


2




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.
Nathaniel Johnston, The Minimal Superpermutation Problem, http://www.njohnston.ca/2013/04/theminimalsuperpermutationproblem/, 2013.


LINKS

Table of n, a(n) for n=0..4.
J. A. Barnett, Permutation Strings
N. Johnston. Nonuniqueness of minimal superpermutations. Discrete Math., 313 (2013), 15531557.


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


AUTHOR

Michael Hamm, Sep 13 2010


EXTENSIONS

Edited and expanded by Nathaniel Johnston, Apr 22 2013


STATUS

approved



