How many bit strings of length 6 either begin with two 0's or end with three 1's

I have this so far:


0 0 X X X X

so: $2^4$ combinations


X X X 1 1 1

So $2^3$ combinations.

Would the answer be the sum of these two?

  • 2
    $\begingroup$ Here's a thought... How many strings start with 00 but also end with 111? $\endgroup$ – Jason Knapp Nov 12 '15 at 15:14
  • $\begingroup$ Is that a typo on the second scenario? Why is that bit string 7 digits long? Once that is straightened out, yes, add those two numbers together and then subtract out the set of numbers you double counted. Can you figure out what that set is? $\endgroup$ – turkeyhundt Nov 12 '15 at 15:17
  • $\begingroup$ Yes it's a typo, so it would be $2^4 + 2^3$, I'm not sure about the set of numbers which are double counted. $\endgroup$ – user20842454566 Nov 12 '15 at 15:19
  • $\begingroup$ Generally $|A \cup B| = |A| + |B| - |A \cap B|$. Look up principle of inclusion and exclusion. $\endgroup$ – Nicholas Nov 12 '15 at 15:24

No, because you have counted $00X111$ twice. It qualifies both ways. You need to subtract out one set.

  • $\begingroup$ What is the set that I subtract? ($2^4+ 2^3 - X?)$ $\endgroup$ – user20842454566 Nov 12 '15 at 15:22
  • $\begingroup$ @user20842454566, because there's only one X in the string 00X111, there are $2^1$ strings of that form, just as you got $2^4$ and $2^3$ for strings of the form 00XXXX and XXX111 in the OP. So the final count is $2^4+2^3-2^1=16+8-2=22$. $\endgroup$ – Barry Cipra Nov 12 '15 at 15:28

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.