Minimal Superpermutation Problem
Question Description
We have $1,2,\ldots,n$ symbols. We want to find a shoretest possible string on the symbols that contains every permutation of those symbols as a contiguous substring. We call a string that contains every permutation in this way a $superpermutation$, and one of minimal length is called a $minimal$ $superpermutation$.
For example, when $n=3$, all permutations are : $123$,$132$,$312$,$213$,$231$,$321$. In this case, the minimal superpermutation is $123121321$. The minimal length is 9.
Minimal Length
An apparent lower bound of the length of superpermutation on $n$ symbols is $n ! +n-1$, because it must contain every permutation of the $n!$ permutations as a substring - the first permutation has $n$ characters to the string, and each of the remaining $n ! - 1$ permutations have a lengh of at least 1 character more. A trivial upper bound on the length of a minimal superpermutation is $ n* n !$
Suppose we already have a small superpermutation on $n$ and we want to construct a small superpermutation on $n+1$ symbols. To do so, simply replace each permutaiton in the $n$ symbol superpermutation by (1) the permutaiton, (2)the symbol $n+1$ (3) that permutaiton again.
You can find detail here: link
Uniqueness
It turns out that there are in fact many superpermutations of the conjectured minimal lengh. The result of [1] shows that there are at least
$\prod_{k=1}^{n-4} (n-k-2)^{k\cdot k!}$