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 
 A: 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$.
A: $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)$).
A: 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.
