[seqfan] Re: A007489 and strings containing all permutations

franktaw at netscape.net franktaw at netscape.net
Sun Feb 21 01:26:36 CET 2010

If it's true, it is certainly worth including as a comment.

If it isn't true, the sequence such shortest lengths is worth including 
as a separate sequence.

If a proof can't be found in a reasonable length of time, it should be 
added as a conjecture.

Franklin T. Adams-Watters

-----Original Message-----
From: Jason Orendorff <jason.orendorff at gmail.com>

I think A007489 gives the length of the shortest string of n symbols 
contains all n! permutations of those n symbols as contiguous 
substrings.  The
first 4 such strings are: 1, 121, 123121321, 
having lengths 1, 3, 9, 33. Neat, huh? It seems interesting enough to 
go in the
entry, if it's true. I think it is; a summary of my argument is posted 


Unfortunately, I can't find a reference for this. All the papers I've
been able to
find are about a different problem, described here:


Surely this is known. Can anyone provide the reference?

Thanks for your time.

Jason Orendorff


Seqfan Mailing list - http://list.seqfan.eu/


More information about the SeqFan mailing list