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.