Given an alphabet with $n$ characters, what is the shortest sequence that contains all $n!$ permutations as subsequences?
A subsequence can be obtained from a sequence by deleting any characters, thus it's different from a substring, whose elements have to be contiguous in the original sequence. I say this because the similar problem of finding the shortest sequence having all permutations as substrings seems to be more studied, but it's different from what I'm asking here.
Some examples of shortest supersequences:
- $n=2\quad-\quad121$ (length 3)
- $n=3\quad-\quad1213121$ (length 7)
- $n=4\quad-\quad1234123142134$ (length 13 – not proven to be shortest).
It's easy to see that $n^2$ is an upper bound, since a sequence
$$12\ldots n\, 12\ldots n\, \ldots\, 12\ldots n $$
($n$ times) contains all permutations. A simple lower bound is $n(n+1)/2$, basically because
$$12\ldots n\; 12\ldots (n-1)\; 12\ldots (n-2)\;\ldots $$
is too short (this can be proven rigorously). Is anything more known about this problem?
The question was asked on stack exchange, but the answer there is far from satisfactory since it gives only a broken link and no reference.
Best Answer
This seems to be an open problem. It is listed in the OEIS as sequence A062714, as noted by Ilya. Summarising the most important results:
Let $m$ be the length of such a sequence. Then Newey (amongst others) describes a simple algorithm to generate them with $$m = n^2 -2n +4.$$ This is not, however, the best one. Radomirovic proves that the shortest sequences obey the tighter upper bound of $$m \le \left\lceil n^2 - \frac73 n + \frac{19}3\right\rceil.$$ A lower bound better than the trivial one shown by OP is given by Kleitman and Kwiatkowski: $$m \ge n^2 - C_\epsilon n^{7/4+\epsilon},$$ for any $\epsilon > 0$.