5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do you define the rank of a permutation? $\endgroup$ – gnometorule May 21 '15 at 16:09
  • $\begingroup$ Gnometorule, I just edited the text, so you can understand now how I define the rank of permutation. $\endgroup$ – Jimbo_ai May 21 '15 at 16:51
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.