8
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ This is not an answer I wanted to leave a comment but I am not given the option for some reason. "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 is the method I tried but I am confused on finding 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. How did you find out it was 7? $\endgroup$ – Kasper-34 Jul 23 '13 at 18:20
  • $\begingroup$ It is always a good idea to try to find alternative ways of computing the results. $\endgroup$ – vonbrand Mar 4 '14 at 14:46
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ nice, that's a good way to think of it. thanks. $\endgroup$ – user56763 Jul 20 '13 at 21:23
  • $\begingroup$ @trichoplax: Thank you for spotting the transposition. I have rewritten the answer, interchanging the roles of $0$ and $1$. $\endgroup$ – André Nicolas Jun 8 '15 at 0:04
  • $\begingroup$ Great - that's even clearer now. $\endgroup$ – trichoplax Jun 8 '15 at 0:09
3
$\begingroup$

I find your second method easier. It is correct.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Here's an approach. Take 5 1s and 2 0s and arrange them any way you like; you can do this in $7\choose2$ ways. Then just insert an extra 1 between the 0s.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This seems to give the number of ways that two 0s can be separated by exactly one 1. The question asks for non-adjacent 0s, which would include all separations (anything from one to six 1s between the 0s). $\endgroup$ – trichoplax Jun 7 '15 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.