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, 153 (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..5.

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.

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

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

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 August 20 12:43 EDT 2014. Contains 245798 sequences.