[seqfan] A007489 and strings containing all permutations
Jason Orendorff
jason.orendorff at gmail.com
Sat Feb 20 02:16:00 CET 2010
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
More information about the SeqFan
mailing list