Superpermutations

Not the regular permutation that you know.

Permutations

You may remember “permutations and combinations” from your maths class. Anyways it’s always great to revise.

Permutations are just like shuffling. So imagine you have 3 cards: 1,2 & 3. The question that a permutation asks is, “In how many ways can you arrange all three cards?”. So let’s do that.

We have
123, 132, 231, 213, 312, and 321.

That shouldn’t be hard. Anyways, the answer is six. You can arrange the cards in one of the above three ways.
That being said I think that’s all I should tell for now. They can be studied in much depth if you want to, so definitely give it a try.

Superpermutations

Superpermutations are quite fancy and as Wikipedia defines it, “a super-permutation on n symbols is a string that contains each permutation of n symbols as a substring.”

To be honest back in 2018, when I read this for the 1st time, it was a bit intimidating. But trust me it got only better. So continue reading.

Now we remember permutations for 1, 2, and 3.
Why don’t we try finding the permutation for 1, and 2?

We get
12 and 21

It was easy.
A super-permutation is a string of numbers that contain all the permutations. A string is a sequence of characters, these characters can be numerical digits, letters, punctuation marks, etc.

That being said, it would mean that the super-permutation of 1 and 2 will be
1221

Well, congratulations. You just found out the super-permutation of 1 and 2.
It would only be logical if we try to find out the super-permutation of 1, 2, and 3. So why wait? Here we go again

The permutations for 1,2 and 3 are:
123, 132, 231, 213, 312 and 321

And after arranging them together we get
123132231213312321

Congratulations on your second super-permutation.

Seriously that’s all, I don’t think it deserves the word “Super”

To be honest I said the same thing. What’s so super in super-permutation? It’s not cool. It’s dumb, arranging all the permutations into a single string. Anyone can do it right.

Let me ask a question, “What is the smallest string that we can write that will contain all the permutations?”

For start let’s do it with 1 and 2:
One of it’s longest super-permutation is 1221.

The smallest super-permutation?
121

Why?
121 contains both 12 and 21 in itself ergo 121 is the smallest string.

Again what’s so super about it you may ask.
Well, why don’t we try it with 1, 2, and 3:
Trust me it’s solvable but not easy.

One of the longest super-permutation is 123132231213312321.

The smallest super-permutation?
123121321

It contains all 6 permutations 123, 231, 312, 213, 213, and 132.

Check it out yourselves.

Yellow: 123
Violet: 231
Red: 312
Green: 321
Purple: 213
Indigo: 132

Note:
You might notice that I was using the words “One of the longest super-permutation”, there’s a reason why I chose to say that. You see each string can be arranged in many ways.
For {1,2}
1221 is one of the longest arrangements.
2112 is another.

The same holds for {1,2,3}.Hence, just to make things clean it’s important to think about everything small revolving around.

For the sake of fun. Let’s consider the superpermutation for {1,2,3,4}

One of it’s longest super-permutation:
123412431342132414231432213421432431241323142341342134123214324131243142412341324231421343124321

And drum roll for the smallest super-permutation for n=4 {1,2,3,4} :
123412314231243121342132413214321

What’s beautiful is that the largest string contains 96 digits, whereas the smallest covers the whole thing using only 33 digits. Isn’t it just fascinating?

To be honest that’s a hell of a solution to a hell of a problem.

Now we can do the same for {1,2,3,4,5}, {1,2,3,4,5,6},….., and {1,2,3,4,5,6,….,n}. But it’s important to look at it real carefully and ask some questions first.

Is there a pattern or formula that we can find for calculating the number of digits in the smallest string for all n, where n is any natural number from 1 to infinity?
Let’s seek the answer.

Finding a Formula

Now before we go further it’s important for you to understand what a factorial is,

Factorial:
Factorial for a positive integer n is denoted by n!
It’s the product of all the positive integers less than n
i.e. n! = n × (n-1) × (n-2) × (n-3) × …………. × 3 × 2 × 1

For example:
3!=3 × 2 × 1 = 6
That’s all you need to know for now.

You can stop reading and try to figure out a formula by yourself if you want to.

For n=1 i.e {1}
There’s only one digit so both the largest and smallest strings will have one digit.

For n=2 i.e {1,2}
The smallest string has 3 digits, which is 121.

For n=3 i.e {1,2,3}
The smallest string has 9 digits, which is 123121321.

For n=4 i.e {1,2,3,4}
The smallest string has 33 digits, which is 123412314231243121342132413214321.

If you look closer
1!=1

1!+2!=3

1!+2!+3!=9

1!+2!+3!+4!=33

It wouldn’t harm if we convert it into a tabular form.

Well, it looks like we found one.

For any n, the smallest string of superpermutation is
1!+2!+3!+4!+….+(n-1)!+n!

The Formula is working right??

Well, we must hold our horses, before announcing everyone that we have discovered a formula for finding the number of digits in the smallest superpermutation for any natural number n we must check it thoroughly.

Let’s do the math and check it for n=5.
For n=5
1!+2!+3!+4!+5! = 153.

And drum roll for the smallest super-permutation string for n=5.

123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321

It’s beautiful….
All 153 digits. And here’s the thing that makes it so awesome, the largest super-permutation string would contain 600 digits, using the formula we just reduced 600 almost to it’s 1/4th.

Hence we have done a pretty good job so far. But just to keep the things safe let’s try the formula for n=6.

For n=6
1!+2!+3!+4!+5!+6!=873

And the number of digits in the smallest super-permutation string for n=6 is, 872
I am sorry to break this to you but this is were our formula fails. But that should not stop you.