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.



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

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

  • $\begingroup$ Thanks a lot for your answer. $\endgroup$ – user62198 Apr 23 '15 at 19:29
  • $\begingroup$ You are welcome. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.