How many $5$-digit numbers (including leading $0$'s) are there with no digit appearing exactly $2$ times? The solution is supposed to be derived using Inclusion-Exclusion.
Here is my attempt at a solution:
Let $A_0$= sequences where there are two $0$'s that appear in the sequence.
…
$A_{9}$=sequences where there are two $9$'s that appear in the sequence.
I want the intersection of $A_0^{'}A_1^{'}…A_9^{'}$= $N-S_1+S_2$ because you can only have at most two digits who are used exactly two times each in a $5$ digit sequence.
$N=10^5$, $S_1=10\cdot \binom{5}{2}\cdot[9+9\cdot 8 \cdot 7]$, and $S_2=10 \cdot 9 \cdot \binom{5}{4} \cdot8$.
The $S_1$ term comes from selecting which of the ten digits to use twice, selecting which two places those two digits take, and then either having the same digit used three times for the other three places, or having different digits used for the other three digits.
The $S_2$ term comes from selecting which two digits are used twice, selecting where those four digits go, and then having eight choices for the remaining spot.
So my answer becomes $10^5 -10 \cdot \binom{5}{2} \cdot [9+9 \cdot 8 \cdot 7]+10 \cdot 9 \cdot \binom{5}{4} \cdot 8$.
Am I doing this correctly?
Best Answer
The structure of the analysis is the same as yours. We count the bad strings, where some digit appears exactly twice.
We first count the strings where say the digit $0$ appears exactly twice. Where the $0$'s are can be chosen in $\binom{5}{2}$ ways. For each of these ways, the remaining $3$ places can be filled in $9^3$ ways.
So our first estimate of the number of bad strings is $(10)\binom{5}{2}(9^3)$.
But we have double-counted, for example, the strings where $0$ and $1$ appear exactly twice. There are $\binom{5}{2}$ ways to choose where the $0$'s go, and for each there are $\binom{3}{2}$ ways to choose where the $1$'s go. The remaining spot can be filled in $8$ ways. Multiply by $\binom{10}{2}$ for the number of ways to choose the two digits that appear twice.
Putting things together, we find that the number of bad strings is $$(10)\binom{5}{2}(9^3)-\binom{10}{2}\binom{5}{2}\binom{3}{2}(8).\tag{1}$$
Finally, subtract (1) from $10^5$.