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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

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

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

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), 91-98.

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

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 November 27 18:17 EST 2014. Contains 250249 sequences.