Q: How many bit strings contain exactly eight $ 0$s and ten $1$s if every $0$ is either immediately followed by a $1$, or this $0$ is the last symbol in the string?
Instructor said the answer was $9^2 \times 8^3 \times7^4 \times 6^5…$
But I don't understand why.
If the string is $0101010101010101$ that leaves two $1$s to place. Aren't there $10$ places to put the two $1$s? After each $1$ and at the beginning or end of the string?
Best Answer
Case 0: The string ends in a 0.
The problem becomes equivalent to counting distinct arrangements of 7 instances of '01' and 3 instances of '1', followed by a '0' at the end. There are $\binom{10}{3} = 120$ arrangements in case 0.
Case 1: The string ends in a 1
The problem is equivalent to counting distinct arrangements of 8 instances of '01' and 2 instances of '1'. There are $\binom{10}{2} = 45$ distinct arrangements here.
Total = $\binom{10}{3} + \binom{10}{2} = 165$.