A superpermutation on 
symbols is a string that contains every one of the 
permutations
of those symbols as a contiguous substring. 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
 |
This length was once conjectured to be minimal for every 
, but Houston (2014) found a shorter superpermutation for 
.
