login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A180632 Minimum length of a word on n letters that contains every permutation (length-n word on distinct letters). 3
0, 1, 3, 9, 33 (list; graph; refs; listen; history; text; internal format)
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!+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).

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

J. A. Barnett, Permutation Strings

Nathaniel Johnston, Non-uniqueness of minimal superpermutations, Discrete Math., 313 (2013), 1553-1557.

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

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

Content is available under The OEIS End-User License Agreement .

Last modified July 28 00:26 EDT 2014. Contains 244987 sequences.