# Counting number of distinct digits in natural numbers less than 1,000,000

• Mar 12th 2009, 08:45 PM
qtpipi
Counting number of distinct digits in natural numbers less than 1,000,000
http://img.photobucket.com/albums/v1...sd/sttreee.jpg

I need to do this for k=2,3 only. Any help? Thanks.
• Mar 12th 2009, 08:53 PM
ThePerfectHacker
Quote:

Originally Posted by qtpipi
http://img.photobucket.com/albums/v1...sd/sttreee.jpg

I need to do this for k=2,3 only. Any help? Thanks.

Let us do k=2 and you try k=3. First pick 2 digits numbers that you are going to use. There are $\displaystyle {9\choose 2}$ ways of doing that. But once you have choose these two numbers there are $\displaystyle \frac{6!}{3!\cdot 3!}$ ways of ordering them. Multiply those two together and you get your answer.
• Mar 29th 2009, 03:30 PM
figs
I have the exact same question, but I have to do it for all 6 values of k. I understand why there are $\displaystyle {9\choose2}$ ways to pick 2 digits, but why are there $\displaystyle \frac{6!}{3!\cdot 3!}$ ways to order them? I've been trying to work the problem out this way:
For each value of k, treat the number of possible numbers as a 6-digit base-k number, subtract the numbers that don't have k distinct digits, and finally multiply it by the number of possible values for each distinct digit. So, for example, if k=4, I'd work it out as:
$\displaystyle {9\choose4} [(4^6 - 1) - (3^6 - 1) - (2^6 - 1) - 4] = 415800$
The number of numbers in a base 4, 6-digit number, minus all the numbers with only 3 distinct digits, 2 distinct digits, and 1 distinct digit, and multiply it by the number of ways to choose those 4 digits.
I know my reasoning is wrong, because when I try the same idea for k=5, I get a value over 1 million, which is obviously impossible.

So how do you calculate the number of ways to order the digits? I get that 6! is because it's a 6-digit number, but what the denominator?

Thanks.