Five digit numbers where each digit can appear up to three times

Question

The question is to determine how many five-digit numbers there are (using the digits 0-9) where each digit can appear up to three times in the number. The total number of numbers that can be made using 0-9 is $10^5$ so that places an upper restriction on the answer. Finding how many there are with no repeated digits is also just a permutation, given by $10!/(10-5)!$. It's also easy to count up how many numbers there are where each digit appears exactly four and exactly five times, and subtract those from $10^5$, which gives 99,540 possible numbers, but I feel this is either wrong or at least a very naive way of doing it. Is there a better way of doing it?

Answer 1

We should form two cases, one of 0 (because 0 can't be the first one) and one with all numbers 1-9, to find out how many numbers there are that use a digit 3 or more times. Then, we can subtract this from 90,000 (the number of five digit numbers). This will give us the desired number.

Case 1: 0 shows up more than 3 times.

When you think about it, the only way 0 shows up more than three times is if the number is 10,000; 20,000; 30,000; etc., up to 90,000. So we just have to add nine to the following case.

Case 2: Some number 1-9 shows up more than 3 times.

This is slightly more tricky. We start with 1, just to make things easy. But when you really start to think about it, 1's would have to fill 4/5 slots in the number for it to break the rules. Therefore, the numbers (if the 5th number is 2) would be as follows:

11112

11121

11211

12111

21111

and we can do the same thing for every other number, 0 and 2-9. However, 01111 does not count, so we have to make sure to get rid of that one as well. Therefore, there are 8 times 5, or 40 ways this can be done for the number 1 for 2-9, and 4 ways this can be done with 0. Overall, the number 1 can be made in 44 different ways. This is also true for 2, 3, 4, 5, 6, 7, 8, and 9 (try plugging them in above where 1 is now). This gives us 9*44 + 9 ways to break the rules, or 9*45 ways. This comes out to 405 ways.

Subtract this from 90,000 and you will see that there are 89,595 ways to accomplish your task.