Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many 4 digit numbers are there which contain not more than two different digits?

As usual, I will highlight my attempt:

  1. I can have 9 numbers using only 1 digit, e.g. $1111, 2222, \dots 9999$ = 9 digits

  2. Using two digits out of 9 (excluding 0) (selected in $\,^{8}C_{2}$ ways), I can arrange them in $4!$ ways. Furthermore, I can use one digit out of the selected 2 once or thrice (e.g. $2111$ or $2221$) or simply both digits 2 times (e.g. $2288$, $6677$). Hence I get: $$\,^{8}C_{2} \times \left(\frac{4!}{2!\times2!} + \frac{4!}{3! \times 1!}\times 2\right) = 392$$

  3. Finally, I consider numbers with zeroes. With zero selected as a digit, I have 9 options for other digits. And using the same logic as in 2) I can have either 1 zero ($8880$), 2 zeroes (e.g. $8800$) or 3 zeroes in a number ($7000$). This gives me $$9\times \left( \frac{4!}{2!\times2!} + \frac{4!}{3!\times1!} + 1\right) = 99$$

the above 3 steps yield a total number of $9+392+99=500$

However, the answer i have with me is $576$.

share|improve this question

2 Answers 2

up vote 6 down vote accepted

André has come up with a nice and simple alternative solution, but I'm going to try to salvage your method, which is essentially correct.

  1. This step does indeed give you 9 numbers.
  2. There are 9, not 8, numbers between 1 and 9, so you want to use $9 \choose 2$ not $8 \choose 2$. Indeed, $${9 \choose 2} \times \left(\frac{4!}{2!\times2!} + 2\times\frac{4!}{3!\times1!}\right) = 504$$
  3. You've counted too many here, because you've not excluded putting the zero first. There are actually only three ways of having one zero (8880, 8808, 8088) and three of having two (8800, 8080, 8008). Hence the total number of ways, including the one way of having three zeroes, is $9 \times (3 + 3 + 1) = 63$.

Now $9 + 504 + 63 = 576$. So you had the right approach, but you just messed up some of the arithmetic.

share|improve this answer
    
thank you for using my method and correcting my mistakes. Thanks a ton! –  Karan Jun 6 '12 at 16:00

We have the $9$ single-digit numbers.

For the others, the first digit can be chosen in $9$ ways. For each of these choices, the "other" digit can be chosen in $9$ ways. For each of these choices, we can have the other digit in $1$, $2$, or $3$ places. These places can be chosen in $\binom{3}{1}+\binom{3}{2}+\binom{3}{3}$ ways, for a total of $7$ (alternately, this can be viewed as $2^3-1$, all but choosing $0$ places for the other digit). This gives a count of $(9)(9)(7)$, which is $567$.

Now add the $9$.

Note that precisely the same procedure works for, say, $17$-digit numbers. Nothing changes, except that the $2^3-1$ is replaced by $2^{16}-1$.

share|improve this answer
    
Elegant solution andre. Thanks. –  Karan Jun 6 '12 at 16:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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