### The Shortest String Containing all Permutations of n Symbols

Posted:

**Thu Feb 17, 2011 6:14 am UTC**Here's an interesting (to me, anyway) combinatorics problem that has a reasonably intuitive answer that I can't for the life of me prove is correct or find a proof of.

What is the length of the shortest string that contains every permutation of the digits 1,2,...,n as substrings?

For example, when n = 2 a minimal string is 121, which contains each of "12" and "21" as substrings. When n = 3, a minimal string is 123121321, which contains each of "123", "132", "213", "231", "312", and "321" as substrings. The length of the shortest such string has been conjectured to be equal to[math]\sum_{k=1}^n k![/math]See the OEIS, MathExchange, StackOverflow and this PDF for similar posts by people asking about this question. Strangely, these are the only sources that I can find that mention this problem, and they all are from last year. Those posts all go into how to construct a string that by all rights seems optimal, and all of those sources conjecture that the given string is indeed of minimal length, but not one of them actually proves it. And I can't seem to prove it either, despite the fact that it looks like it should fall to a simple induction argument.

So my question is -- is the conjecture true? Is the conjectured "optimal" string of length [imath]\sum_{k=1}^n k![/imath] actually optimal?

I believe the reason the conjecture is more difficult to prove than would be expected is because there seems to be some sort of shift in behaviour of the optimal strings around n = 5 or n = 6, at which point it becomes infeasible to brute force what the optimal strings are, and the strings are so long as to be difficult to work with.

For example, via brute-force you can show that for n = 1,2,3,4 the optimal string has length 1,3,9,33, follows the construction given in the posts linked above, and furthermore is unique (up to requiring that the string starts with "123...n"). However, when n = 5 there are two optimal strings that start with "12345", and when n = 6 there are at least 96 distinct strings of the conjectured minimal length.

So does anyone have any insights on this problem or any other references that I'm not aware of? Cheers.

What is the length of the shortest string that contains every permutation of the digits 1,2,...,n as substrings?

For example, when n = 2 a minimal string is 121, which contains each of "12" and "21" as substrings. When n = 3, a minimal string is 123121321, which contains each of "123", "132", "213", "231", "312", and "321" as substrings. The length of the shortest such string has been conjectured to be equal to[math]\sum_{k=1}^n k![/math]See the OEIS, MathExchange, StackOverflow and this PDF for similar posts by people asking about this question. Strangely, these are the only sources that I can find that mention this problem, and they all are from last year. Those posts all go into how to construct a string that by all rights seems optimal, and all of those sources conjecture that the given string is indeed of minimal length, but not one of them actually proves it. And I can't seem to prove it either, despite the fact that it looks like it should fall to a simple induction argument.

So my question is -- is the conjecture true? Is the conjectured "optimal" string of length [imath]\sum_{k=1}^n k![/imath] actually optimal?

I believe the reason the conjecture is more difficult to prove than would be expected is because there seems to be some sort of shift in behaviour of the optimal strings around n = 5 or n = 6, at which point it becomes infeasible to brute force what the optimal strings are, and the strings are so long as to be difficult to work with.

For example, via brute-force you can show that for n = 1,2,3,4 the optimal string has length 1,3,9,33, follows the construction given in the posts linked above, and furthermore is unique (up to requiring that the string starts with "123...n"). However, when n = 5 there are two optimal strings that start with "12345", and when n = 6 there are at least 96 distinct strings of the conjectured minimal length.

So does anyone have any insights on this problem or any other references that I'm not aware of? Cheers.