How many bit strings of length 8 with exactly two 0's are there for which the 0's are not adjacent?
I'm having a lot of trouble with this seemingly simple problem.
I'm trying to do this with stars and bars. Am I correct or on the right track at least?
First, I put two bars in for my two 0's, and then put one 1 in between them to make sure the 0's are not adjacent.
|x|
This leaves me with 5 more 1's to place in the bit string. example: x|xx|xxx would be one distribution of the 5 remaining 1's.
So, this gives me c(3+5-1,3-1), or c(7,2)=21 ways.
The only other way I could think to do this problem would be to get the total # of ways to have a bit string of length 8 with exactly two 0's, and subtract the total number of ways to have the 0's be adjacent.
So, c(8,2) for the total number of was to have exactly two 0's, and subtract the total number of ways I can have exactly two 0's in a bit string where the 0's are adjacent which is 7.
This gives me c(8,2)=28 and 28-7=21. This confirms my answer (if either of these methods are correct that is).
Thanks!
Best Answer
Both your approaches are right. Perhaps you will find the following approach easier.
Put down our $6$ ones, like this: $$1\qquad 1\qquad 1\qquad 1\qquad 1\qquad 1$$ There are $7$ places where $0$'s could go, the $5$ gaps between $1$'s and the $2$ ends. We must choose $2$ of these places, so the answer is $\binom{7}{2}$.
This generalizes immediately to say a bit string of length $16$, with $5$ $0$'s no two of which can be adjacent.