Number of five digit numbers that can be formed with this condition

Question

Question: How many five digit numbers can be made having the digits 1,2,3 each of which can be used at most thrice in a number?

I did it by assuming that there are 9 digits that can be used (3 '1's, 3 '2's and 3 '3's). The first place can be filled in 9 ways, the second place can be filled in 8 ways and so on. I got 15120 as the answer.

Answer 1

Unfortunately, you're making distinctions where there aren't any--for example, one digit $1$ is the same as any other, though it may have a different meaning once we choose a place for it.

The first thing I notice about this problem is that, if I want to directly count the desired numbers, there will be several cases and subcases. We could start with the case of no $1$s (with subcases two $2$s and three $2$s), then the case of a single $1$ (with subcases one $2,$ two $2$s, and three $2$s), and so on. That seems like a pain, though.

More straightforwardly, we could figure out how many five-digit numbers can be made from only digits in $\{1,2,3\},$ then figure out how many of these we don't want--that is, those with four or more $1$s, $2$s, or $3$s--and subtract it from the total.

Hopefully the following facts are clear:

• There are $3^5=243$ five-digit numbers with only digits in $\{1,2,3\}.$
• Our "bad" numbers can only break one rule at a time--so we can't, for example, have more than three $1$s and more than three $3$s in a five-digit number--so we won't have to worry about over-counting our "bad" numbers.
• There are exactly the same amount of numbers with too many $1$s as there are with too many $2$s, and as there are with too many $3$s.

How many break the rule with too many $1$s? Well, only one can have all $1$s, but what about four $1$s? Well, we know that such a number has to have exactly one place that doesn't have a $1,$ and there are two choices for what can be in this place. Can you take it from there?

Answer 2

As Mauve suggested in the comment, you could count the bad numbers and subtract their number from the total number of $3^5$. Bad numbers are of the form $xxxxx$ (which can be constructed in only $3$ different ways) of $xxxxy$ and its $5$ permutations (which can be chosen in $3\cdot 2\cdot 5$ ways), so the total number will be $3^5 - 3 - 30 = 210$.

Also, you can go the straight-forward way. The feasible numbers contain

1. two digits once and one digit three times
2. one digit twice and another digit three times
3. two digits twice and one digit only once

Counting the combinations for all three cases, we get:

1. $3$ ways to chose the number that will appear tree times, $4$ positions to place the lower of the remaining numbers and $5$ positions to place the last one, a total of $3\cdot 4\cdot 5 = 60$ different mumbers.
2. $3$ ways to chose the digit that will appear tree times, $2$ ways to choses the other contained digit and $\binom{4}{2}+\binom{4}{1} = 10$ ways to place them between the other digits (they are allowed to appear side by side), making a total of $3\cdot 2\cdot 10 = 60$ different numbers.
3. $3$ ways to chose the digit that will appear only once, $5$ ways to chose its position in the number and $\binom{4}{2} = 6$ ways to chose the positions of the lower remaining digits, making a total of $3\cdot 5\cdot 6 = 90$ different numbers.

Summing up the three results, we do of course obtain the same result from above: $60+60+90=210$.