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

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

$9\times C(5,2)\times (8\times 7\times 6 + 8\times C(3,2)\times 7)$ should be $9\times C(5,2)\times (8\times 7\times 6 + 8\times C(3,2)\times 7/2)$ because we count numbers $aabbc$ twice -- one for $a$ first and another for $b$ first, so 52920 is the right answer (I mean "first" corresponding to $9\times C(5,2)$).

• Thanks a lot for your answer. I see the mistake now. – user62198 Apr 23 '15 at 19:30
• We can also count numbers in which two digits appear twice as $\binom{9}{2}\times 7 \times \frac{5!}{2!2!}$ – anir123 Apr 17 '17 at 19:19

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$.

• Thanks a lot for your answer. – user62198 Apr 23 '15 at 19:29
• You are welcome. – André Nicolas Apr 23 '15 at 21:22

The way I did it was to count the compliment like some one did before but I set it up as follows: 9( C(5,3)*81 + C(5,4)*9 + C(5,5))

Then I did the total 9^5 minus that. That basically let there be at least three of a number which is required for a fail.