Partial Superpermutation-Personal Research

Research Paper: https://drive.google.com/file/d/1uJBwfoomedSucuqDxd72wBhbHTzoVLaG/view?usp=sharing

In 2006, an anime series called Haruhi was released. However, there was one confusing aspect about it. It was the fact that the 14 episodes of the first season were not aired in linear order. When the DVD of this series became available, the episodes were rearranged. This made the fans become interested in watching this TV series in every possible permutation or arrangement of episodes, maybe this would allow the fans to see the storyline from a different perspective. However, if the fans were to watch each permutation separately, that is to finish watching one arrangement of the episodes and than start watching another arrangement of episodes, finish it, start watching a new arrangement and so on, then it would take around 12204960768000 minutes or more than 23 million years considering the fact that an episode was around 10 minutes long. If this super long series of every permutation of episodes being separated started playing since humans first appeared on earth, we would not be one third of the way from watching all the permutations separately. So would the Haruhi fans have to be really lucky to find the secret arrangement which the producers believed that the first season of Haruhi has to be watched (if there is such an arrangement)? Is there a quicker way to watch all permutations of episodes? Clue, consider the fact that I mentioned ‘separately’ several times.

If you have figured out how to approach the problem above, then try to solve this riddle. A species of aliens comes to earth and threatens to destroy the earth the next minute. However, the aliens give us a chance and will not destroy the earth if we manage to type an ordered string which contains a permutation of the first 5 positive integers. While the aliens are kind enough to not make us have to do this with 14 characters, unlike Haruhi producers, note that writing the all the permutations of the first 5 positive integers separately will take

5! x 5 = 600 characters. Let’s assume that no one in the world could type something that long in a minute. What is the shortest answer which will guarantee that the correct permutation is in the answer?

If you know about superpermutations, you could save the earth (unfortunately you can not be the hero of Haruhi fans, yet). A superpermutation of n symbols is a string which contains all the permutations of those n symbols as a substring. The permutations are allowed to overlap, for example the 121 contains both permutations of the first 2 positive integers, 12 and 21. This topic has been researched even before the Haruhi TV series as it was first thought about in the 1990’s. The approach we talked about on writing the permutations separately is the idea of a trivial superpermutation. For all values of n > 1, there is a shorter way to write a superpermutation than to write the trivial superpermuation.

The first 4 superpermutations are 1, 121, 123121321 and 123412314231243121342132413214321 each with a length of 1, 3, 9 and 33. Have you found a pattern within these numbers? Clue, the one we are looking for is not a polynomial.

While there are infinitely many functions f(x) which f(1) = 1, f(2) = 3, f(3) = 9 and f(4) = 33, one interesting observation made by mathematicians is that these numbers follow the pattern of

1! + 2! + … + n!, they are the sum of the factorials of the first n factorials. That was easy, then why can I not be the hero of Haruhi fans? This is because when this conjecture was made, it was difficult to test this conjecture even for values like 5 and 6. Even today, it is quite hard to look through all possible strings which could be candidates for the shortest superpermutation. When

n = 6, although 1! + 2! + 3! + 4! + 5! + 6! = 873, in 2014 a superpermutation n = 6 of length 872 was found.

Wait, before we move on, how exactly was the sum of the factorials of the first n factorials found? Why was it chosen over from the infinitely many functions which could have satisfied the conditioned written above? Maybe it looked the most simple, but interesting? The answer is that this formula was given from an algorithm.

The image above illustrates how the algorithm works. You start off with the superpermutation n = 2 which is 121. After that, you split the superpermutation into the permutation it consists of. You will then duplicate the permutations, add the 3 and then squeeze the result back together in order to make use of overlaps. This will give 123121321 which is a shortest superpermutation n = 3. Something similar could be done in order to get from a superpermutation n = 3 to n = 4, n = 4 to n = 5 and so on. This formula is recursive, meaning that you use the result you have in order to create the next result.

So how does using this formula to get a superpermutaion n = a into n = a + 1 increase the length by (a + 1)! ? Before I tell the answer, try to figure it out. Try to at least get an understanding of why this is the case and if you are familiar with induction, use induction to prove this. One tip, try to take note of what increases/decreases the length and how much it increases/decreases the length by.

The answer is that when we bring the superpermutation n-1 back into the permutations it consists of, we get (n-1)! x (n-1) characters. However when we overlap the same adjacent permutations back together, we will remove exactly the same amount of characters. When we duplicate the permutations, we get (n-1)! x (n-1) characters. We also will get (n-1)! of the new character n. This gives 2(n-1)! x (n-1) -(n-1)! x (n-1) + (n-1)! = (n-1)! x (n-1) + (n-1)! = n!.

As mentioned, this recursive formula does not give the shortest superpermutation when n is greater than 5. Although there have been some more accurate formulas such as n! + (n–1)! + (n–2)! + (n–3)! + n-3 for values of n greater than or equal to 7.

What if the fans of Haruhi suddenly obsessed over watching every triplet of the 14 episodes given that the order does matter? How many episodes would they have to watch? The answer is probably smaller than you think with the answer being 2186 episodes.

How do we know this? This is a basic application of partial superpermutations. The reason why the answer could be smaller than you thought is because we were able to take advantage of several overlaps between each adjacent partial permutations.

So what is a partial permutation? This is something that you probably would have learned if you have prepared for math competitions or even in the probability unit in maths class. The term partial permutations is a bit ambiguous and not used that frequently, but it is basically an ordered subset with a certain number of elements of a set. This simple question will illustrate the idea of a partial permutation: You have 7 books and you want to pick 5 to arrange them in a bookshelf, how many ways can you do this?

The answer is 7! divided by (7–5)! which is 2520. Do not get this mixed up with the idea of combinations which are similar, but the order in which the objects are arranged does not matter.

Now that you hopefully got an idea of what a partial permutation is, we could start discussing partial superpermutations. A partial superpermutation is a string which contains all partial permutations. The number of elements which are picked to create the partial permutation will be referred to as k and the number of total elements will be referred to as n.

There is a formula for the shortest partial superpermutation for some values of k. However, the formula might not be valid for all values of n for several values of k even if n is greater than or equal to k. However, there is a conjecture(similar to the idea of hypothesis) which I made that after a certain value of n, the length of the shortest partial superpermutation will follow a certain formula. The value of n depends on the value of k.

When k = 1 and 2, the formula mentioned above does work for all values of n, as long as n is an integer greater than or equal to k. For example, when k = 1, we are looking at partial superpermutations which have a length of 1. This is basically the same as each individual element of a set with distinct elements. The shortest string containing all of these permutations will have a length of n. If we were to substitute 1 into k in the conjecture formula, we will get n. For all values of n, this formula works. The same goes for k = 2, where the formula is n² — n + 1. The proof of this formula is in the research paper, but it would take too long to explain here. If we were to substitute 1 into k in the conjecture formula, we will get n² — n + 1. This works for all values of k. However, when we get to k = 3, the formula does not always work. Substituting 3 into k in the conjecture formula gives us n³ — 3n² + 2n + 2. However when n = 3, the formula gives 8 even though when n = 3 k = 3, the shortest partial superpermutation is 123121321 which has a length of 9. I believe that larger values of k will experience the same problem. One quick way to show this is that the shortest partial superpermutation will have the length given in the conjecture formula in the case that there is an overlap of k-1 elements between all adjacent partial permutations. Partial superpermutations where n = k are basically superpermutations of n. Clearly, after a certain value (3) of n, it is not possible for the adjacent permutations to have n-1 elements overlapping.

In order to apply the idea of partial superpermutations in order to help solve the shortest superpermutation problem, we will have to investigate the reason why some values of n do not follow the formula. If there are more than 1 value of n which does not follow the formula, it could be worth observing, how much they are off from the formula and try to find a pattern in how much they differ. However, there are some limitations to this, it would be challenging to find and confirm a shortest partial superpermutation possibly once k > 5 as the shortest superpermutations n > 5 are not proven.

Another possible area to investigate on partial superpermutations is the number of distinct partial superpermutation of the shortest length. This idea has been investigated in superpermutations.

I would like to thank Mr. Sparks for introducing me to the idea of superpermutations. I would also like to thank Ms. Dale for showing me some resources which helped me with this research project.