page_title: Superpermutation
hierarchical_section_title: Superpermutation
caption_attribution_description: English: The smallest superpermutation of three symbols; each permutation is set above where it can be found on the superpermutation, which is at the bottom.
context_page_description: 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 because overlap is allowed. For instance, in the case of n = 2, the superpermutation 1221 contains all possible permutations, 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!. 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:
  12345123415234125341235412314523142531423514231542312453124351243152431254312
  1345213425134215342135421324513241532413524132541321453214352143251432154321
context_section_description: 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 A180632 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):
  12345123415234125341235412314523142531423514231542312453124351243152431254312
  1345213425134215342135421324513241532413524132541321453214352143251432154321
  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.
caption: The distribution of permutations in a 3 symbol superpermutation.
exif: {}