Results 1 to 11 of 11

Math Help - how many numbers less than or equal to N with all digits unique

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    Delhi
    Posts
    3

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Mar 2008
    From
    Pennsylvania, USA
    Posts
    269
    Thanks
    37

    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Mar 2008
    From
    Pennsylvania, USA
    Posts
    269
    Thanks
    37

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

    Quote Originally Posted by richard1234 View Post
    ^Up to N. N can be some arbitrary number other than a power of 10.
    Well, of course -- I was just offering a start.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2012
    From
    Delhi
    Posts
    3

    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Mar 2008
    From
    Pennsylvania, USA
    Posts
    269
    Thanks
    37

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2013
    From
    Croatia
    Posts
    24

    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).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,904
    Thanks
    764

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

    Quote Originally Posted by abender View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,904
    Thanks
    764

    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 9\dfrac{9!}{(10-k)!} k-digit "unique numbers". This means there are 9\sum_{i = 1}^k \dfrac{9!}{(10-i)!} "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 N = \sum_{i = 1}^k d_i 10^{i-1}, \quad \forall 0< i < k, d_i \in \mathbb{Z}, 0\le d_i \le 9;\quad 0< d_k \le 9. Next, let A_i = \{z \in \mathbb{N} \mid z\mbox{ is a "unique number" with }i\mbox{ digits} \}. For any z\in A_k, we can refer to its digits with the notation z = \sum_{i = 1}^k z_i 10^{i-1}. Next, define the sets N_i = \{z\in A_k \mid z_i > d_i \mbox{ and } \forall i < j \le k, z_j = d_j \} for 1 \le i \le k. What elements are in these sets?

    So, by construction, the number of "unique numbers" up to N is given by \sum_{i = 1}^k \left( |A_i| - |N_i| \right) (let me know if you have any questions about why this is true). We already know how to calculate |A_i| easily. So, how do we calculate |N_i|? That is a little more difficult. To make this easier, we will want one more thing. For notation, let [n] = \{1,2,\ldots, n\} (this is fairly common notation in combinatorics). Let M = \left\{i \in [k] \mid \sum_{j = 0}^{k-i} d_{k-j} 10^j \in A_i \right\}. What is this set M? What does it represent? More specifically, what is \min(M)?

    Spoiler:
    I plugged in the formula for \sum_{i=1}^k |A_i| into wolframalpha and it shot out 9\left( 986410 - \dfrac{362880e\Gamma(8-k,1)}{(9-k)!} \right) where \Gamma(n,x) is the incomplete upper gamma function. Probably not terribly useful, but interesting that there is a continuous function based on k. Makes me wonder if we plug in \log_{10}(N) for k, how close will we come to the actual number?
    Last edited by SlipEternal; October 8th 2013 at 07:46 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,904
    Thanks
    764

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

    Quote Originally Posted by kicma View Post
    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 \{1,2,3,4,5,6,7,8,9\}. The last digit is an element of \{1,3,5,7,9\}. 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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Oct 2012
    From
    Ireland
    Posts
    597
    Thanks
    165

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

    Put your numbers into binary to simplify the problem :P
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 10th 2012, 10:12 AM
  2. Replies: 1
    Last Post: August 29th 2011, 02:18 AM
  3. Sum of digits of numbers between 1 to n
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 29th 2010, 04:36 AM
  4. Unique sum for all natural numbers
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 3rd 2010, 11:41 AM
  5. Replies: 2
    Last Post: April 3rd 2007, 12:31 PM

Search Tags


/mathhelpforum @mathhelpforum