Permutations & series

Question

Consider all the $7$ -digit numbers containing each of the digits $1,2,3,4,5,6,7$ exactly once, and not divisible by $5$. Arrange them in decreasing order. What is the $2015$th number (from the beginning) in this list?

Answer 1

The biggest numbers on the list will start with 7 and have some permutation of the other digits for the rest, except 5 can't be in the final place. There are 6! - 5! = 720 - 120 = 600 of these (subtract 5! to exclude the 5! numbers that look like 7XXXXX5). There will be the same amount starting with 6, but starting with 5 there will be 6! = 720 since we don't have to exclude any. So far that accounts for 600+600+720=1920 numbers, which is almost 2015, so the number we want must start with 4.

There are 5!-4! = 96 numbers that look like 47XXXXX and don't end with 5, and the smallest such number (4712356) will be number 1920+96 = 2016 on the list. So the number we want is the next smallest such number, or 4712536.

Answer 2

Let's count. If it's not divisible by 5, then 5 cannot be the last digit. If we have to arrange $n$ digits, such that one of them is not the last, we have $n-1$ ways to pick the last, and then $(n-1)!$ ways to pick the remaining ones, so a total of $(n-1)!(n-1)$. So, in total we have $6\cdot 6!=4320$ combinations.

Now, the largest numbers have 7 in front. How many are there? Well, I need to rearrange the remaining 6 digits, without putting 5 last. So I have $5\cdot 5!=600$ combinations. Next, we have the ones starting with 6. That gives use another 600 combinations (we're up to 1200 numbers in the list). Then the ones starting with 5 (another 600, up to 1800). Since the last one starting with 4 will take us to the 2400 in the list, the 2015th must start with 4.

Now we need to find the 2015-1800=215th number starting with 4. Ok, we do the same calculations in this sublist. First numbers will be 47*****, and there are $4\cdot4!=96$. Then 46*****, another 96 numbers (we're up to 192). So the 215th will be of the form 45*****.

Now we need to find the 215-192=23th number in this sublist. Notice that now we already used 5, so after fixing the 3rd number, we have 4! combinations. First we will have 457****, and there are $4!=24$. Therefore your number is the second to last of this sublist!

Last: 4571236

Second to last: 4571263

There you are: it's 4571263...unless I miscounted. =P

Edit: I made a mistake in my argument, after fixing 5 as the second number. I hope it's fixed correctly now.