Minimal Superpermutation Problem

Question Description

We have $1,2,\dots ,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\ast 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!}$

Reference

1. Non-uniqueness of minimal superpermutation