Superpermutation

In combinatorial math, a superpermutation is a list of numbers that contains each different arrangement of symbols it is made up of inside of it. While superpermutations can simply be made up of every arrangement listed side by side, it can also be shorter. Sometimes, the arrangements may overlap. For example, when there are 2 different symbols, the superpermutation 1221 contains all possible arrangements, 12 and 21. The list 121 also contains both permutations, 12 at the beginning and 21 at the end.

As the number of symbols increases, the length of the superpermutation increases, too. The superpermutation with only 1 symbol is only 1 long (1), while the 2nd superpermutation is 3 long (121). The 3rd superpermutation is 9 long (123121321), and the 4th one is 33 long (123412314231243121342132413214321). The length of the superpermutation with 5 symbols is 153, and it looks like this:^[1]

123451234152341253412354123145231425314235142315423124531243512431 52431254312134521342513421534213542132451324153241352413254132145 3214352143251432154321

Six or more symbol superpermutations[change | change source]

Right now, mathematicians do not know what the smallest superpermutation is when there are six or more symbols. However, over time the choices of what they could be have narrowed considerably from both above and below.

In September 2011, an unknown person on the internet forum 4chan showed people that there was definitely a smallest superpermutation for any superpermutation with more than 1 symbol. On the website, it was called "The Haruhi Problem", from a Japanese anime called The Melancholy of Haruhi Suzumiya. It was phrased like this: what would be the shortest amount of episodes that you would need to watch in order to guarantee that you watched every episode of a show? In October 2018, mathematician Robin Houston tweeted about it.^[2]^[3]

On October 25, 2018, Robin Houston, Jay Pantone, and Vince Vatter made the unknown person's proof better and posted it to the mathematics community.

On October 20 2018, Greg Egan found smaller superpermutations for ones with six or more symbols than there had ever been.^[4] This shows that smallest superpermutation must be at most that size.

As time goes on, people think that the smallest and largest possible lengths for these superpermutations will be narrowed down further. There is only one definite smallest superpermutation for each number of symbols.