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

November 10th 2012, 11:52 AM

abender

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

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

November 10th 2012, 12:22 PM

richard1234

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

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

November 10th 2012, 01:22 PM

abender

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

Quote:

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.

November 10th 2012, 09:36 PM

anantkaushik89

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

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?

November 11th 2012, 05:45 AM

abender

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

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.

October 8th 2013, 04:21 AM

kicma

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

I have a similar problem.

How many are there odd 4-digit numbers with all digits different?

Is it 9*8*7*5? I get that when I first choose last and first digit. But if I start from the beggining I get 9*9*8*5 (because 0 can't be first so there are again 9 possibilities for second digit).

October 8th 2013, 04:44 AM

SlipEternal

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

Quote:

Originally Posted by abender

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.

Be careful when working with these. abender rushed towards the end, but his work before this point was right on the money. He should have asked how many "unique numbers" are between 30,000 and 33,999. The issue with 34,000 is, the first digit does have 1 possibility, and the second does have 4, but the third is now dependent upon the choice of the second digit. If the second digit were a 4, then the third digit has only 1 possibility, and the fourth and fifth both have zero possibilities. So, the second digit actually has only 3 possibilities.

October 8th 2013, 07:09 AM

SlipEternal

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

As abender already mentioned, since a number with 11 or more digits is guaranteed to repeat a digit by the Pigeonhole Principle, there are no "unique numbers" with 11 or more digits. Generalizing abender's algorithm, there are k-digit "unique numbers". This means there are "unique numbers" with k or fewer digits.

As another method of counting, suppose N has k digits. Start with the set of all "unique numbers" with k or fewer digits. Then subtract off the number of "unique numbers" where the first digit is greater than the first digit of N. Then subtract off the number of "unique numbers" where the first digit is equal to the first digit of N and the second digit is greater. Etc. So, to describe the algorithm, you can use this type of notation.

Let . Next, let . For any , we can refer to its digits with the notation . Next, define the sets for . What elements are in these sets?

So, by construction, the number of "unique numbers" up to N is given by (let me know if you have any questions about why this is true). We already know how to calculate easily. So, how do we calculate ? That is a little more difficult. To make this easier, we will want one more thing. For notation, let (this is fairly common notation in combinatorics). Let . What is this set ? What does it represent? More specifically, what is ?

Spoiler:

I plugged in the formula for into wolframalpha and it shot out where is the incomplete upper gamma function. Probably not terribly useful, but interesting that there is a continuous function based on . Makes me wonder if we plug in for , how close will we come to the actual number?

October 8th 2013, 07:27 AM

SlipEternal

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

Quote:

Originally Posted by kicma

I have a similar problem.

How many are there odd 4-digit numbers with all digits different?

Is it 9*8*7*5? I get that when I first choose last and first digit. But if I start from the beggining I get 9*9*8*5 (because 0 can't be first so there are again 9 possibilities for second digit).

Let's look at the starting conditions. Before choosing any digits, the first digit is an element of . The last digit is an element of . Hence, if you choose the first digit first, and you choose an odd digit, you will only have four choices available for the last digit. On the other hand, if you choose the last digit first, no matter which digit you choose leaves only 8 choices left for the first digit. If you want to count from left to right, you need to break it up into a LOT of cases. You could choose one odd digit among the first three, two odd digits among the first three, or three odd digits among the first three. This becomes too cumbersome. Alternately, you can choose the digits right to left. Then you have five choices for the first digit, 9 choices for the second, 8 for the third, but you either have 7 or 6 choices for the last depending on whether you chose a zero yet or not.

So, as a general rule of thumb, choose the digits in the order of how restricted they are. The last digit is the most restricted, so choose that first: 5 choices. After that choice, before making any others, you have 8 possible choices for the first digit (since an odd digit is now out) or you have 9 choices for either of the other two digits (since they can still be zero). So, again, choose the most restricted. So now, you have 5*8 to choose the last digit then the first digit. Now, the remaining two digits are equally restricted with 8 choices each. So, to choose the last digit, then the first digit, then the second digit, there are 5*8*8 different choices. Finally, to choose the 3rd digit, there are 7 choices, and the total number of odd 4-digit numbers with distinct digits is 5*8*8*7.

October 9th 2013, 10:55 AM

Shakarri

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

Put your numbers into binary to simplify the problem :P