Combinatorics on words | Permutations | Enumerative combinatorics
Superpermutation
In combinatorial mathematics, a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring. While trivial superpermutations can simply be made up of every permutation listed together, superpermutations can also be shorter (except for the trivial case of n = 1) because overlap is allowed. For instance, in the case of n = 2, the superpermutation 1221 contains all possible permutations (12 and 21), but the shorter string 121 also contains both permutations. It has been shown that for 1 ≤ n ≤ 5, the smallest superpermutation on n symbols has length 1! + 2! + … + n! (sequence in the OEIS). The first four smallest superpermutations have respective lengths 1, 3, 9, and 33, forming the strings 1, 121, 123121321, and 123412314231243121342132413214321. However, for n = 5, there are several smallest superpermutations having the length 153. One such superpermutation is shown below, while another of the same length can be obtained by switching all of the fours and fives in the second half of the string (after the bold 2): 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321 For the cases of n > 5, a smallest superpermutation has not yet been proved nor a pattern to find them, but lower and upper bounds for them have been found. (Wikipedia).
