I have this question. Apparently my solution is wrong and I want to know why it's wrong. The question is:
How many different passwords of length $10$ have $3$ A's and $7$ digits such that no two A's are adjacent? The digits are from $0-9$.
My solution:
_A_A_A_ thus $x_1 + x_2 + x_3 + x_4 = 7$, where $x_2 \geq 1$ and $x_3 \geq 1$
Therefore, there are $7-1-1 = 5$ (identical) digits to put in $4$ distinct spots.
Using combination with repetition formula: $(5+4-1)C5 = 8C5$
Then since there are $10$ digits, with repetition allowed, there are $10^7$ ways.
Answer: $8C5 \cdot 10^7$
But apparently this answer is wrong. Can someone please provide the correct step-by-step solution for this problem and where I went wrong?
As @JMoravitz stated in the comments, your answer is correct. Let's confirm it.
Method 1: We use the Inclusion-Exclusion Principle.
We choose three of the ten positions for the $A$s, then fill each of the remaining positions with one of the ten digits, which can be done in $$\binom{10}{3}10^7$$ ways. From these, we must subtract those arrangements in which at least one pair of $A$s are adjacent.
A pair of $A$s are adjacent: We have to arrange nine objects: $A$, $AA$, and seven digits. There are nine ways to choose the position of the $A$ and eight ways to choose the position of the $AA$. Each of the remaining seven positions can be filled with a digit in $10$ ways. Hence, there are $$9 \cdot 8 \cdot 10^7$$ such arrangements.
However, if we subtract the number of arrangements with a pair of $A$s from the total, we will have subtracted too much since we will have subtracted each arrangement with two pairs of consecutive $A$s twice, once for each way of designating one of the pairs as the pair of consecutive $A$s. We only want to subtract such arrangements once, so we must add them back.
Two pairs of adjacent $A$s: Since we only have three $A$s, this can only occur if we have the block $AAA$. We have eight objects to arrange: $AAA$ and the seven digits. There are eight ways to place the block $AAA$. Each of the remaining seven places can be filled with a digits in $10$ ways. Hence, there are $$8 \cdot 10^7$$ such arrangements.
By the Inclusion-Exclusion Principle, the number of admissible arrangements is $$\binom{10}{3}10^7 - 9 \cdot 8 \cdot 10^7 + 8 \cdot 10^7 = \left[\binom{10}{3} - 9 \cdot 8 + 8\right]10^7 = (120 - 72 + 8)10^7 = 56 \cdot 10^7 = \binom{8}{5}10^7$$
Method 2: We arrange the seven digits, then insert the $A$s in the spaces between them or at the ends of the row.
Since we have $10$ choices for each of the seven digits, we can arrange seven digits in a row in $10^7$ ways. This creates eight spaces, six between successive digits and two at the ends of the row. $$\square d_1 \square d_2 \square d_3 \square d_4 \square d_5 \square d_6 \square d_7 \square$$ To separate the $A$s, we must choose three of these eight spaces in which to place an $A$, which can be done in $\binom{8}{3}$ ways. Hence, there are $$\binom{8}{3}10^7 = \binom{8}{8 - 3}10^7 = \binom{8}{5}10^7$$ admissible arrangements.