# Number of $10$ digit numbers such that every digit that appears appears exactly twice

I need to find the number of $10$-digit numbers in which every digit that appears appears exactly twice.

I have attempted to solve this but am not sure if I am not overcounting something.

The only problem is that a $0$ cannot stand on the leftmost position.

The first digit, say $i$, can be chosen in $9$ ways. Then, there are $9$ remaining places for the second $i$.

Now, we have $9$ possible remaining digits and $8$ remaining places. We need to choose $4$ digits, we can do so in $\binom{9}{4}$ ways.

Now, the remaining places must be divided into two-element subsets, which can be done in ${8\brace 2}$ ways (Stirling numbers of the second kind).

Finally, we only need to distribute these $4$ numbers between these subsets, in $4!$ ways.

And so the final answer is: $$9 \cdot 9 \cdot \binom{9}{4} \ {8 \brace 2} \cdot 4!$$ Is it the correct answer?

• Did you mean to write $9 \cdot 9 \cdot \binom{9}{4} {8 \brace 2} \cdot 4!$? Jun 9, 2018 at 12:11
• Of course. thanks. Jun 9, 2018 at 12:12
• For each digit to appear twice, you need twenty digits.... Jun 9, 2018 at 12:14
• @LordSharktheUnknown You compose a number of five different digits, each of them appears exactly twice. Jun 9, 2018 at 12:16
• $\left\{8\atop2\right\}$ is the number of ways to partition an $8$-element set into two (non-empty) subsets, not into subsets of two. Jun 9, 2018 at 12:19

For the moment, forget the stipulation that we avoid a leading zero. Then there are $\binom{10}5$ choices for the five digits involved. Then the number of ways of assembling two each of these five digits into a string is the multinomial coefficient $\binom{10}{2,2,2,2,2}=10!/2^5$. So, allowing a leading zero, there are $$\binom{10}5\frac{10!}{2^5}=\frac{10!^2}{5!^22^5}$$ possibilities.
But the probability one starts with a zero is the same as the probability one starts with any digit, so the final answer is $9/10$ of this, namely $$\frac 9{10}\times\frac{10!^2}{5!^22^5}.$$
If we repeatedly (five times) pick the most significant not yet determined digit and then the position of its twin, we end up with $$9\cdot 9\cdot 9\cdot 7\cdot 8\cdot 5\cdot 7\cdot 3\cdot 6\cdot 1 =25719120$$ possibilities
Since the leading digit cannot be $0$, there are $9$ ways to pick the leading digit. There are $9$ ways to pick the other location for the leading digit. There are $\binom{9}{4}$ ways to select which four of the other nine digits appear in the number. There are $\binom{8}{2}$ ways to select the locations of the smallest of those numbers, $\binom{6}{2}$ ways to select the locations of the next smallest of those numbers, $\binom{4}{2}$ ways to select the location of the third smallest of those numbers, and $\binom{2}{2}$ ways to select the location of the largest of those numbers. Hence, the number of $10$-digit positive integers in which every digit that appears appears exactly twice is $$\binom{9}{1}\binom{9}{1}\binom{9}{4}\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2}$$ As Joriki pointed out in the comments, ${8 \brace 2}$ is the number of ways of placing $8$ objects in two non-empty subsets, not the number of ways of placing eight objects in four subsets of size $2$, which is $$\frac{1}{4!}\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2}$$ If you replace your factor of ${8 \brace 2}$ by the above factor, your answer would agree with mine.