Nine digit positive integers of the form PQRSTUVWX are called four-six numbers if the digits P, Q, R and S (in this order) are in strictly ascending order of magnitude, while the digits S, T, U, V, W and X (in this order) are in strictly descending order of magnitude.

For example, each of 567876543 and 678986430 is a four-six number, but 567876654 is NOT a valid four-six number since the digits 876654 (in this order) are not in strictly descending order of magnitude. Similarly, 678875432 is NOT a valid four-six number since the digits 6788 (in this order) are not in strictly ascending order of magnitude.

All the possible four-six numbers are now arranged in descending order of magnitude.

What is the 4664^th number?

Note: No four-six number can contain leading zeroes.

I found it easier to count in ascending order. If the 4th digit is d, there are C(d-1,3) choices for the first 3 digits, and C(d,5) for the right 5. So the total number of "four-six" numbers is

Sum[C(d-1,3)C(d,5),{d,5,9}] = 9500.

We therefore want the 9500+1-4664=4837th number in increasing order.

If the first digit is 1, there are C(d-2,2)C(d,5) numbers with 4th digit d. So the number of numbers with first digit 1 is Sum[C(d-2,2)C(d,5),{d,5,9}]=3735. Similarly, there are Sum[C(d-3,2)C(d,5),{d,5,9}]=2595 numbers starting with 2. We therefore want the 4837-3735=1102nd number starting with 2.

If the second digit is 3, there are Sum[C(d-4,1)C(d,5)]=930 numbers. If the second digit is 4, there are Sum[C(d-5,1)C(d,5)]=720 numbers. We therefore want the 1102-930=172nd number starting with 24.

There are Sum[C(d,5),{d,6,9}]=209 numbers starting with 245. So we want the 172nd number starting with 245.

Since Sum[C(d,5),{d,6,8}]=83, we want the 172-83=89th number starting with 2459.

There are C(d,4) numbers starting with 2459d, so the number of numbers starting with 2459 below 2459d is C(4,4)+...+C(d-1,4)=C(d,5). Since C(8,5) = 56 < 89 < C(9,5), we want the 89-56=33rd number starting with 24598.

Similarly, since C(6,4)=15 < 33 < C(7,4), we want the 33-15=18th number starting with 245986, the 8th number starting with 2459865, the 2nd number starting with 24598654, the first number starting with 245986541. Phew!
Edited on March 17, 2008, 2:56 am

Posted by Eigenray on 2008-03-17 02:52:41