[James]: Not just regular permutations, super-permutations, “can leap tall buildings in a single bound” permutations.
What is a super-permutation? First of all let’s talk about an ordinary permutation.
A permutation is just like a shuffle, so imagine I had three cards: 1, 2, and 3.
How many ways can I shuffle those three cards, so let’s do that?
These are the permutations: 1,2,3,
and we could have 1,3,2, 2,1,3, 2,3,1,
and we could have 3,1,2 & 3,2,1. There are six permutations that use the numbers 1 to 3,
and that is three factorial (“3!”).
Just to remind people, 3 factorial means 3×2×1,
and that’s because we've got three choices for the first one,
two choices for the second one,
and one choice for the last one.
And you multiply those choices together, that’s 3 factorial.
That’s 6. There are 6 ways to do it.
Now, a super-permutation is a string of numbers that contains all the permutations,
so the super permutation of 1, 2, & 3 would have
all the permutations of 1, 2, & 3 contained within it, so we could just string these together.
Now, that’s simple right?
1,2,3, 1,3,2, 2,1,3, 2,3,1, 3,1,2, 3,2,1
So, that’s a super-permutation; it has length 18. You don’t seem that impressed with that super-permutation.
It doesn’t deserve its name as being super? Okay, we can do better.
What is the smallest string of numbers that we can write that contains all of the permutations?
Well, how about this one: 1,2,3, 1,2,1, 3,2,1.
Alright this has length 9,
but it is a super permutation, and it’s the shortest super-permutation using 1,2,3.
Let’s check, so it has—
[Brady]: So, you’ve used overlaps, basically?
[James]: I have used overlaps. Let’s check.
1,2,3, that’s in there.
1,3,2, I’ve got it here.
2,1,3, where is it? There it is.
2,3,1, right there near the beginning.
3,1,2, I bet that is here.
And, 3,2,1 is right at the end.
Yes it contains all the permutations, but it is the shortest string that contains all the permutations, and it has length 9.
So let’s have a look at the shortest super-permutations for all the values: 1–3, 1–4…
Let’s have a look! So they start with 1.
Okay.
The super-permutation containing all the permutations of 1 is…
1.
And let me just check.
Yes, that contains all the permutations; it has length 1.
Great well what is the super permutation for…
1 and 2?
It is 1,2,1.
So it has 1 & 2, and it has 2 & 1. That’s all you need, and that has length 3, as you can see.
Now for 3, we’ve done that one, and we have a super permutation of length 9.
Now 4. I’m gonna tell you, 4 has length 33, so let’s have a look at what that looks like.
1,2,3,4...2,1,3,2...1,4,3,2,1. There we go.
So that has length 33, and it contains all the permutations.
So, 5. What is the super permutation of 5? It has length 153.
Should I write that one out?
[Brady]: No, it’s escalating.
[James]: It is escalating, and then for 6…
don’t know.
[Brady]: No!
[James]: We don’t know!
What is the super-permutation, or the minimum super-permutation, using 1–6?
We have a guess.
Okay, so there is a pattern of maybe this guess is right.
Have a look, this first number.
It was 1. That is 1 factorial.
The second number is 3. Actually that turns out to be 1! + 2!.
9: 1! + 2! + 3!
You might notice a pattern.
4: 33. Well that is 1! + 2! + 3! + 4!
What do you guess 5 is going to be?
[Brady]: Hmm, 1–5, all factorials.
[James]: Yeah.
1! + 2! + 3! + 4! + 5! is 153.
So, six…
What do you guess six is going to be, adding up the factorials?
Let’s do it. 1! + 2! + 3! + 4! + 5! + 6! = 873
I think that’s a pretty good guess for the minimum length of the super-permutation using 1–6.
Unfortunately, recently,
someone found a super-permutation that is shorter.
In fact, they found a super-permutation that had length 872.
1 shorter! The pattern did not hold! It was 1 shorter!
And I can show you what that looks like!
This is it on the screen.
[Brady]: No way!
[James]: And we still don’t know if that’s the shortest one.
We still don’t know if the answer is 872.
It’s possible there is a shorter one out there.
It was a little bit of a shock.
Well, you can see this pattern,
and there’s a reason why you would think this pattern would hold.
There is a way to construct the next super-permutation from the previous one,
and if you construct it in that way, then absolutely the super permutation will have that length.
And,
so they were just thinking well that must be the minimum length.
This shows they were wrong. It isn’t the minimum length.
It is not necessary for it to be the minimum thing.
Now, you can see that this might become harder, the larger these numbers become.
It’s actually computationally hard.
So, maybe we’ll find what the minimum length is for 6,
but then, we’ll have to work out 7 and so on, and this is going to get harder and harder,
unless…
we find some clever construction of the minimum super-permutations
that tells us what the minimum length is.
This is worth comparing to something called De Bruijn sequences,
and De Bruijn sequences are a similar idea, but they contain all the sequences.
Using – let’s say – one to three, you would contain all the sequences. It would look like this.
So here’s a De Bruijn sequence.
Similar idea: 1,1,1, 2,1,1, 3,1,2, 2,1,2, 3,1,3, 2,1,3, 3,2,2, 2,3,2, 3,3,3,1,1.
So here we have a sequence and it contains all sequences of length three using the numbers 1–3.
So, 1,1,1 is in there.
1,1,2 is in there.
3,3,3 is in there.
3,1,3 is in there.
So De Bruijn sequences are a lot like super-permutations,
but the sequences inside are allowed to contain duplicates,
but we have a way to construct De Bruijn sequences,
and it constructs the minimum-length De Bruijn sequence as well.
And they have practical applications in robotics and in actually lots of other areas as well.
DNA sequencing and all lots of unexpected applications.
So, De Bruijn sequences, although I think should be harder really, are completely understood,
but super permutations are still a little bit mysterious.
[Brady]: The Great Courses Plus is an on-demand video service with lessons and courses taught by leading professors
from universities and institutions all around the world.
They’ve got an extensive library of 8,000 videos,
covering pretty much anything that might take your fancy, from playing chess to the geography of Antarctica
I’m actually heading to Antarctica myself in the next few weeks, so I’ve been paying particularly close attention to those lessons.
[embedded video]: It’s about 50% larger than the United States including, Alaska
[Brady]: They’re really good, really in-depth stuff.
[embedded video]: If all of this ice melted, the global sea level would rise about 60m. That’s 200ft.
[Brady]: But whatever you’re into, you’re gonna find something really good here. Learn at your own pace. No homework.
No teachers telling you off.
But new stuff being added to the site every month.
For a free trial on The Great Courses Plus, and to show some support for Numberphile, go visit
https://thegreatcoursesplus.com/numberphile
That’s the address there.
Our thanks to them for supporting this episode!