[Math] How many 5 digit numbers can be formed out of {1,2,3…,9} where a digit can repeat at most twice

combinatoricspermutations

The question is: How many different numbers of 5 digits can be generated out of {1,2,3,4,5,6,7,8,9} such that no digit can appear more than twice ? That is a number like 11213 is not allowed. but 12345, 11224 etc are allowed.

For 3 digit numbers,I argued as follows: without any restriction on repetition, there are 9^3 possibilities, which is equal to 9x8x7 + 9xC(3,2)*8 + 9(where C(3,2) is 3 choose 2). In this case the answer is 9^3-9. [Note: 9x8x7 is where no repetitions are allowed, 9xC(3,2)*8 is where 1 digit can repeat exactly twice, 9 is where all digits are repeated]

However, for the 5 digit case, I argued similarly but getting wrong answer. Here is what I did.

for no repetitions: 9x8x7x6x5; only one digit repeats exactly twice: 9xC(5,2)x[8x7x6 + 8xC(3,2)x7 ] ; only one digit repeats exactly thrice: 9xC(5,3)x8x8 ; similarly 9xC(5,4)x8 and finally just 9 (for all repetitions).

So if this is correct, then 9^5 = 9x8x7x6x5 + 9xC(5,2)x[8x7x6 + 8xC(3,2)x7] + 9xC(5,3)x8x8 + 9xC(5,4)x8 + 9 and my answer should be: 9^5 - [9 + 9xC(5,4)x8 + 9xC(5,3)x8x8]

Unfortunately, L.H.S is far less than R.H.S

I am over counting somewhere but couldn't figure it out.

Any explanation or correct answer would be greatly appreciated.

Thanks

Best Answer

Your cases approach will work. For no repetitions, the number is clearly $9\cdot 8\cdot 7\cdot 6\cdot 5$.

For a single repetition, the repeated digit can be chosen in $9$ ways. For each way, its locations can be chosen in $\binom{5}{2}$ ways, and for every such way the empty spots can be filled in $8\cdot 7\cdot 6$ ways.

Double repetition is a little trickier. The two fortunate digits can be chosen in $\binom{9}{2}$ ways. For each such way, the locations of the larger digit can be chosen in $\binom{5}{2}$ ways, and then the locations of the smaller one can be chosen in $\binom{3}{2}$ ways. The remaining empty spot can be filled in $7$ ways.

Remark: We can alternately count the complement. This avoids the trickiness of the double repetition count, where it is all too easy to overcount by a factor of $2$. There are $9$ sequences with all entries the same. For $4$ the same and $1$ different, we have $9\cdot \binom{5}{4}\cdot 8$ choices. For $3$ the same and $2$ different, we have $9\cdot \binom{5}{3}\cdot 8\cdot 7$. And finally for $3$ the same and $2$ the same we have $9\cdot \binom{5}{3}\cdot 8$.