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
So far, mathematicians have not been able to find the smallest length superpermutation that uses 6 or more symbols. They are slowly getting closer to finding it out.
Six or more symbol superpermutations
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.
Superpermutation Media
The distribution of permutations in a 3-symbol superpermutation
Related pages
References
- ↑ Nathaniel Johnston. (2013). Non-Uniqueness of Minimal Superpermutations. Retrieved 28 January, 2019.
- ↑ Griggs, Mary Beth. "An anonymous 4chan post could help solve a 25-year-old math mystery". The Verge.
- ↑ Houston, Robin. "A curious situation. The best known lower bound... (1054637891085918209)". Twitter. Retrieved 27 October 2018.
- ↑ Egan, Greg (20 October 2018). "Superpermutations". Retrieved 27 October 2018.
Other websites
- The Minimal Superpermutation Problem - Nathaniel Johnston's blog
- Grime, James. "Superpermutations - Numberphile" (video). YouTube. Brady Haran. Retrieved 1 February 2018.