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?

Permutations

Background

We know how to figure out the number of ways to organize distinct things if there are sufficient places for them (such as books on a shelf) from the Factorials entry. But what if there are more spots than there are things? Or more things than spots?

Question

An action figure collector has ten figures to put into a display case, but the case only holds eight figures. In how many ways can the collector display eight figures in the case? 

What if the collector has a display case that holds twelve figures? Now how many ways can the collector display the collection? 

Answer

 

Analysis

Remember from the Factorials entry that we can figure out the number of ways to arrange things by multiplying all the natural numbers up to the number given. For instance, if there were ten spots in the case, we could simply say that there are 10! = 3,628,800 ways to arrange the figurines. Unfortunately, we don't have 10 spots - we only have 8.

So how would this work? Well... we can put any of the 10 figures into that first display slot. And then any of the remaining 9 in the next slot. And then any of the remaining 8 in the next slot. And so on. We end up with:

10 x 9 x 8 x 7 x 6 x 5 x 4 x 3

which will take a minute to work out on a calculator, but we can do it the long way:

10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 = 1,814,400

What would be great is if we could use factorials to calculate this. And it turns out we can.

Remember that 10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1

To get from 10! to what we want, we need to get rid of the 2 x 1. Notice that that is the same as 2!. And so we can get to the number we want by doing this:



Ideally, it'd be great to put this into terms that are in the question - 10 figurines and 8 spots. Well, we can:



If we call the number of figurines n and the number of spots k, we can express the general formula this way:



This is called a permutation and we can notate the calculation this way (there are several ways it can be notated - this is just one):



Another way to do it is this way:

nPk

And so our first question can be expressed as:



So what happens if the reverse happens and there are 10 figurines but 12 slots?

Well... we can't simply do what we did above - that will leave 2 display slots unaccounted for. But what we can do is to look at the problem in reverse and see that when we place the first figurine, there are 12 spots we can put it into. And then we place the next figure and there are 11 slots to choose from. And so on, so that we end up with:

12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3

and this is the same thing as:



This highlights an important concept: 

Vocabulary used:

• Factorial - the calculation that allows for multiplying counting numbers up to a given number n, symbolized as n!

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

Where might you have come from?

Fact-orials Index

Combinatorics:

• Factorials

Where might we go?

Combinatorics:

• Superpermutations