5

I have a problem regarding permutations. When the rank of an unknown $S_7$ permutation is given, I want to find this permutation, but I can not.

For example, I have the following questions:

Find the $S_7$ permutation which has I) rank(1000) II) rank(2000).

Apart from the answers to these examples, I am asking for the methodology to find next time this permutation.

I am looking forward to read your answers.

Thank you for your help in advance!

Note: Writing rank I mean the position where the permutation is, ordering all the permutations in ascending order. For example I have the $S_3$ permutation (213). Its rank is 3, because all the $S_3$ permutations in ascending order are as follows: {123,132,213,231,312,321}. So, we write rank(213) = 3.

Jesse P Francis
  • 1,469
  • 3
  • 27
  • 71
Jimbo_ai
  • 87

1 Answers1

7

How many permutations are there which begin with $1$? If we fix the first digit to be $1$, then we have to arrange the other six numbers in the other six slots. There are $6! = 720$ ways to do that.

Similarly, there are $720$ permutations which start with $2$, so permutations $1$ through $720$ start with $1$ and $721$ through $1440$ start with $2$. The permutation of rank $1000$ starts with $2$.

Fixing the first digit to be $2$, we find that for each digit $d$ (from $\{1,3,4,5,6,7\}$), the number of permutations which start $2d$ is $5! = 120$ (we have to arrange the remaining $5$ digits in the remaining $5$ slots). So $721$ through $840$ start with $21$, $841$ through $960$ start with $23$, and $961$ through $1080$ start with $24$. Thus the permutation of rank $1000$ starts with $24$.

You can carry on this way, zeroing in on $1000$. I'll leave it to you to finish the problem.

Alex Kruckman
  • 76,357