A superpermutation on 
distinct symbols is a string that contains every one of
the 
permutations of those symbols as a contiguous substring,
where 
is a positive integer. A shortest superpermutation
has minimum length among all such strings.
For example, the literal strings 1, 121, and 123121321 are shortest superpermutations on one, two, and three symbols, respectively. The last contains the six permutations 123, 231, 312, 213, 132, and 321 as contiguous substrings. A shortest superpermutation on four symbols is
 |
which has length 33. The minimum lengths begin 1, 3, 9, 33, 153, ... (OEIS A180632; Honner 2019).
A recursive construction gives superpermutations of length
 |
Houston (2014) refuted the conjecture that this length is minimal for every positive integer 
by finding a shorter superpermutation for 
.
