The question in full goes as follows:

How many $5$-digit numbers can be formed from the integers $1,2,\dots,9$ if no digit can appear more than twice? (For instance, $41434$ is not allowed.)

I put my answer as the sum of three subsets (no repetition, one pair, and two pairs). The number of possibilities for no reps is $9\cdot8\cdot7\cdot6\cdot5$. The # of possibilities for one pair is $\binom94$. If there's a pair, then there are $4$ distinct digits in the $5$-digit number. Multiply this by $5!/2$, since each digit will need a place, which is calculated by $5!$. Divide by $2$ to remove redundancy of the digits in the pair. Likewise, the third set goes $\binom93\cdot5!/(2\cdot2)$. The sum of the three subsets being:

$$9\cdot8\cdot7\cdot6\cdot5 + \binom94\cdot\frac{5!}2 + \binom93\cdot\frac{5!}{2\cdot2}$$

The answer at the back of the book goes:

There are $\binom52\cdot8\cdot7\cdot6$ numbers in which only one specified digit appears twice, so there are $9\cdot\binom52\cdot8\cdot7\cdot6$ numbers in which only a single digit appears twice. There are $7\cdot5!/(2!\cdot2!)$ numbers in which two specified digits appear twice, so there are $\binom92\cdot7\cdot5!/(2!\cdot2!)$ numbers in which two digits appear twice. Thus, the answer is

$$9\cdot8\cdot7\cdot6\cdot5 + 9\binom52\cdot8\cdot7\cdot6 + \binom92\cdot7\cdot\frac{5!}{2\cdot2}$$

The answer makes sense to me, but mine doesn't seem wrong either. Both answers don't equal the same, so I wanted to know if someone could point my error in thinking.

  • $\begingroup$ Welcome to MSE! It really helps readability if you format your questions using MathJax. Regards $\endgroup$ – Amzoti Feb 8 '13 at 19:23

In the case of four distinct digits, after you choose the four digits (in $\binom94$ ways), you must choose which of the four is to be repeated; since you can do this in $4$ ways, the actual number of unordered hands in this case is $4\binom94$, not $\binom94$. The factor of $\frac{5!}2$ to account for the order of the cards is fine.

Similarly, in the third case there are $\binom93$ sets of three distinct digits, but this doesn’t tell you which digit is the singleton; there are $3$ ways to choose it, so the actual number of unordered hands in this case is $3\binom93$. Here again your accounting for order is just fine.

  • $\begingroup$ That makes a lot of sense. Thanks. $\endgroup$ – user61519 Feb 8 '13 at 20:37
  • $\begingroup$ @user61519: You’re welcome. $\endgroup$ – Brian M. Scott Feb 8 '13 at 20:41

The number of possibilities of 4 digits with 1 pair repeated is not $9 \choose 4$. You have to first choose the repeated digit ($9$ choices), and then the other 3 distinct digits (${8 \choose 3}$ choices). This accounts for the extra factor of 4 that you are missing in the second case.

Similarly, your third case is missing a factor of 3.


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.