# My answer to a combination problem is different from the textbook answer.

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.

-
Welcome to MSE! It really helps readability if you format your questions using MathJax. Regards – 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.

-
That makes a lot of sense. Thanks. – user61519 Feb 8 '13 at 20:37
@user61519: You’re welcome. – 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.

-