[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