Thread: how many numbers less than or equal to N with all digits unique

Hi all

I am not sure whether this would count as a puzzle but it has puzzled me. I am really bad at combinatorics and need some help. I have stumbled on to the problem which states that

"How many numbers upto N have all unique digits in them?"

eg - suppose N = 34. Then answer is 31 (11, 22, 33 excluded, so 34 - 3 = 31). How do I solve this for a generic case? I cant understand how to extend the idea for 3 digits and above numbers.

Any help would be appreciated. And please do explain your answer to. I would really be thankful for any help which can improve my combinatorics?

Thanks
Anant

Good afternoon from the States.

How many 2-digit numbers do NOT contain any repeating digits? Since a two-digit number is not going to begin in zero, there are 9 permissible values for the first digit, namely one through 9. Zero is allowed for the second digit, but remember that the second digit cannot be the same as the first. Thus, there are 9 permissible values for the second digit. There are therefore 9*9=81 two-digit numbers in which both digits are unique.

What about 3-digit numbers? Same concept: There are 9 permissible values for the first digit (all but zero), 9 permissible values for the second digit (all but the first digit), and 8 permissible values for the third digit (all but the first and second digits). Thus, the answer for the 3-digit case is 9*9*8=648.

Four digits follows similarly: 9*9*8*7.

Clearly, 10 digits is the maximum if you need all digits to be unique. In that case, you get 9*9*8*7*6*5*4*3*2*1. Note that the cases for 9 digits and ten digits are identical.

Hopefully this helps. Please ask if you have any further questions.
-Andy

^Up to N. N can be some arbitrary number other than a power of 10.

Originally Posted by richard1234

^Up to N. N can be some arbitrary number other than a power of 10.

Well, of course -- I was just offering a start.

Thanks abender. I have been able to understand when N is power of 10. What isnt clear is suppose N is something like 34523. Then how do i proceed?

N=34523

For communication purposes, let's call numbers that have all unique digits "unique numbers".

When N=9999, we have 9*9*8*7 = 3888 "unique numbers".

For N=29999 we have the 3888 "unique numbers" that are under 10000, and we now need to consider the unique numbers between 10000 and 29999. The number of "unique numbers" between
10000 and 29999 is found this way: There are 2 choices for the first digit, 9 for the second, 8 for the third, 7 for the fourth, and 6 for the fifth; 2*9*8*7*6 = 6048. So, when N=30000 (which doesn't change the answer from 29999), the number of "unique numbers" is 3888+6048 = 9936.

So know there are 9936 "unique numbers" for N=29999 (or N=30000). Now, how many "unique numbers" are between 30000 and 34000. The first digit has 1 possibility, the second has 4, the third has 8, the fourth has 7, and the fifth has 6, totaling 1*4*8*7*6 = 1344 "unique numbers". So there are 9936+1344 "unique numbers" for N=34000.

Continue in this fashion.