1

Suppose I have a random permutation of first $N$ natural number, how do I determine its index of a given permutation, if all the permutations were arranged in lexographical order ,

I understand the approach for $N<10$ as all numbers are single digit:

 rank=1

 for all positions in permutation:

   rank+= (no of avalable choices for this pos) X (n-present pos)!)

What about when $N>10$ , Example $N=100$. Is it same as for $N<10$.

Vinyl_cape_jawa
  • 4,794
user2970016
  • 33
  • The fact that the numbers are single digits is completely irrelevant. Do you see why? Where is it used that the numbers have only one digit? – Matt Samuel Oct 07 '15 at 22:12
  • Lexicographical rank of 15 is less than 9 or say 8 , would that not effect the above formula where for each position we see how many numbers lexographically less than present numbers are avaliable(i.e not already used) – user2970016 Oct 07 '15 at 22:30
  • Position does not refer to the position of the digit. It's referring to the position of the number in the permutation considered as a sequence. – Matt Samuel Oct 07 '15 at 22:31
  • Yes, the key is how you define lexicographic order. By mathematicians, lexicographical order is usually define so that $(15, 1, 2, 3...)$ is after $(2,3,\dots)$. – Thomas Andrews Oct 07 '15 at 22:40

1 Answers1

0

Suppose that $p_1p_2\ldots p_n$ is a permutation of $[n]=\{1,\ldots,n\}$; we need to count the permutations of $[n]$ that precede it in lexicographic order. There are $p_1-1$ members of $[n]$ smaller than $p_1$, and each of them can be extended to a permutation of $[n]$ in $(n-1)!$ ways; that accounts for $(p_1-1)(n-1)!$ permutations preceding ours. Now what about the ones that start with $p_1$ but then have a second element smaller than $p_2$? There are $(p_2-1)$ such second elements, and each can be followed by any of the $(n-2)!$ permutations of the remaining $n-2$ elements of $[n]$, so that adds another $(p_2-1)(n-2)!$ permutations of $[n]$ that precede ours, bringing the total so far up to

$$(p_1-1)(n-1)!+(p_2-1)(n-2)!\;.$$

Now just continue with the same reasoning: nowhere does it depend on the elements of $[n]$ being single-digit numbers.

Brian M. Scott
  • 616,228