If all 720 permutations of 123456 are put in numerical order, what is the 407th pemutation?

Let's first look at the question coming from the other direction. What permutation is, say 365241? We can see in this example that as prior to this permutation there are all the ones starting with 1 or 2, plus some more. The ones that start 1 or 2 number 2*5!, as the remaining five digits after either the 1 or the 2 can be rearranged in 5! permutations. But also some permutations beginning with 3 also precede 365241. How many? Those beginning 31, 32, 34, and 35 certainly, and some beginning 36. The ones beginning with one of the former group of four pairs number 4*4! as each of the four pairs can be followed by any permutation of the remaining 4 digits. Note that in each position the choices contributed to the total are the digit in the given position minus 1 minus the number of digits to the left which are lower than this digit, all multiplied by the factorial of the number of digits remaining. Thus in the next position, 5 - 1 - 1 (as there is one digit, the three, preceding the 5 lower than 5) is multiplied by 3!. The 5 - 1 - 1 = 3 accounts for beginnings of 361, 362, and 364, each with 3! permutations available for the later digits. Thus the number of permutations of the first six digits that lexicographically precede 365241 is given by:

2*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0! = 357,

so that 365241 is the 358th permutation of the first 6 digits in lexicographical order.
Going in the reverse direction, we can see that the first 5! of the 6! permutations are devoted to those beginning with the digit 1. The next 5! to those with 2, etc. We merely need to divide by 5!: the quotient is the factor of 5! to use; the remainder is further divided by 4!, and the quotient there is the factor of 4!, etc. Thus if we wish to know the 358th permutation of the six digits, we divide 357 (the number of permutations prior) by 5!, giving a quotient of 2 and a remainder of 117; when this is divided by 4! we get 4 with a remainder of 21; when that's divided by 3! we get a quotient of 3 with a remainder of 3. Continuing in this fashion we get as quotients the entire sequence of coefficients of the factorials shown above:

2, 4, 3, 1, 1, 0 (by the way the last one is always zero)

From this sequence we can reconstruct the permutation: There are 2 digits with lexicographic priority over (lower than) the first digit, which must therefore be 3. Of the digits other than 3, there are 4 with priority over the second digit, which is therefore 6. Of the digits other than 3 or 6, three have priority over the third digit (these three therefore being 1, 2, and 4) so the third digit is 5. Of the digits other than 3, 6, and 5, only one has priority over the fourth digit, which is therefore 2. Of the digits other than 3, 6, 5, and 2, only one has priority over the next, which is therefore 4. You can see where we go from there in reconstructing the original 365241.
Now to get back to the originally proposed 407th permutation of the first 6 digits in lexicographical order:

406/5! = 3 with remainder 46
46/4! = 1 with remainder 22
22/3! = 3 with remainder 4
4/2! = 2 with remainder 0

The series of coefficients is therefore 3, 1, 3, 2, 0, 0.

So 3 are prior to the first digit which is therefore 4.
Then 1 previously unused (1) are prior to the second digit which is therefore 2.
Then 3 previously unused (1, 3, 5) are prior to the third digit which is therefore 6.
Then 2 previously unused (1, 3) are prior to the fourth digit which is therefore 5.
Then 0 previously unused are prior to the fifth digit which is therefore 1.
Then the remaining digit is 3.

The reconstructed permutation is therefore 4, 2, 6, 5, 1, 3 as being the 407th in lexicographic (or 426513 numeric) order.

This can be verified via the "brute force" method of invoking the PERMUTE function (Permutations) 406 times starting with "123456".

Posted by Charlie on 2003-07-23 09:44:07