Superpermutations

Background

We covered permutations, so what about putting all those strings of permutations together to get a single string that has all the permutations in it?

Question

What is a super permutation? How many terms do I need to express one?

Answer

It's a string of terms that list every single permutation in it. 

The number of terms needed is at least n! + (n-1)! + (n-2)! + n - 3 

Analysis

Let's talk about a permutation, say like 3P3. There are 6 permutations:

123
132
213
231
312
321

If I want to express all of the permutations in a single string of characters, I could do it this way (I'll add in spaces so you can see the 6 smaller strings in there):

123 132 213 231 312 321

This is called a Super Permutation. So that's 18 terms to express the 6 strings - which is a lot of terms! But this is the maximum number of terms I need in order to express the 6 strings (this is known as the Upper Bound).

Can I make the list more efficient? Yes!

I can start with the first string:

123

and then by simply adding a 1, I'll also have the 231 string:

1231

and then if I add a 2 onto the end of that, I'll have the 312 string:

12312

5 terms expressing 3 strings - pretty good! But now what? I can't simply add a 3 - that doesn't result in a new term. And adding a 2 doesn't result in a new term. So let's add a 1:

123121

and from here I can now add a 3 to get 213:

1231213

and now a 2 for 132:

12312132

and lastly a 1 for 321:

123121321

I've express all 6 permutation strings in 9 terms - which is way better than than 18!

As the number of terms within a permutation increase, the question becomes "What is the minimum number of terms I need (also known as the Lower Bound) to express the super permutation?"

And this is where things get interesting.

Trying to figure out this Lower Bound figure has been one of the challenges in the mathematical community for the past few decades. And then an anonymous user on the forum 4chan started working on an application of this question by trying to figure out the following question:

"I like an anime series that has 14 episodes. It involves time travel and other factors, and so the series need not be watched in any particular order. What is the minimum number of episodes of the series must I watch in order to watch every possible permutation of the series?"

This user essentially asked about the super permutation of n = 14.

And this person answered it, including with a proof.

At the same time academic mathematicians were trying to figure out the problem came across this proof on 4chan and saw that the proof worked. The academics wrote a paper to show this proof and this anonymous 4chan user is listed as the lead author on the paper (the link is listed below).

The proof showed that the Lower Bound of a super permutation is:

n! + (n-1)! + (n-2)! + n - 3

In our example above where we had n = 3 and had a string of 9 terms to express the super permutation, does it check out? Yes:

3! + 2! + 1! + 3 - 3 = 6 + 2 + 1 + 3 - 3 = 9

And just for fun, what about that anonymous 4chan user  - how many episodes, at a minimum, must be watched to watch every possible permutation?

14! + 13! + 12! + 14 - 3 = 93,884,313,611 episodes.

Vocabulary used:

For more information check out these links (comment to add your favourite link):

The IFLS article that talks about the research and paper
The actual academic paper

Where might you have come from?

Fact-orials Index

Combinatorics:

• Permutations

Where might we go?