[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:


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

More information about the SeqFan mailing list