Nine digit positive integers of the form PQRSTUVWX are called foursix 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 foursix number, but 567876654 is NOT a valid foursix number since the digits 876654 (in this order) are not in strictly descending order of magnitude. Similarly, 678875432 is NOT a valid foursix number since the digits 6788 (in this order) are not in strictly ascending order of magnitude.
All the possible foursix numbers are now arranged in descending order of magnitude.
What is the 4664^{th} number?
Note: No foursix number can contain leading zeroes.
I found it easier to count in ascending order. If the 4th digit is d, there are C(d1,3) choices for the first 3 digits, and C(d,5) for the right 5. So the total number of "foursix" numbers is
Sum[C(d1,3)C(d,5),{d,5,9}] = 9500.
We therefore want the 9500+14664=4837th number in increasing order.
If the first digit is 1, there are C(d2,2)C(d,5) numbers with 4th digit d. So the number of numbers with first digit 1 is Sum[C(d2,2)C(d,5),{d,5,9}]=3735. Similarly, there are Sum[C(d3,2)C(d,5),{d,5,9}]=2595 numbers starting with 2. We therefore want the 48373735=1102nd number starting with 2.
If the second digit is 3, there are Sum[C(d4,1)C(d,5)]=930 numbers. If the second digit is 4, there are Sum[C(d5,1)C(d,5)]=720 numbers. We therefore want the 1102930=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 17283=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(d1,4)=C(d,5). Since C(8,5) = 56 < 89 < C(9,5), we want the 8956=33rd number starting with 24598.
Similarly, since C(6,4)=15 < 33 < C(7,4), we want the 3315=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 20080317 02:52:41 