3
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thank you for using my method and correcting my mistakes. Thanks a ton! $\endgroup$ – Karan Jun 6 '12 at 16:00
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Elegant solution andre. Thanks. $\endgroup$ – Karan Jun 6 '12 at 16:00
0
$\begingroup$

Though Andre put a nice idea,I am skeptical about its validity in larger digits.Anyways for this ,here is the solution:

For single digit,there will be nine numbers having a single digit. For two digits, there will be two types of numbers : abbb & aabb. First let's choose two digits,it can be done in C(10,2) ways.

Now for first type abbb, arrangement of digits can be done in { 2xfac(4)/fac(3)}.Here, we have first shuffled both digits in abbb and then divided by fac(3).Also,the two digits we chose can alternately take the variable a & b.

Now,for the type aabb, we will first shuffle the digits i.e fac(4) and the divide them by fac(2) two times.(cos there are 2 a's & 2 b's).Guess why ,we are not here multiplying by 2.

So the answer will be :

9 + C(10,2) x{ [(2xfac(4)/fac(3))] + [fac(4)/(fac(2)xfac(2))] }

$\endgroup$

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.