[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 
that
contains all n! permutations of those n symbols as contiguous 
substrings.  The
first 4 such strings are: 1, 121, 123121321, 
123412314231243121342132413214321,
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 
here:

  http://bit.ly/9h917c

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:

  http://garden.irmacs.sfu.ca/?q=op/smallest_universal_supersequence

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