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$ Nov 12, 2015 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$ Nov 12, 2015 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$ Nov 12, 2015 at 15:19
  • $\begingroup$ Generally $|A \cup B| = |A| + |B| - |A \cap B|$. Look up principle of inclusion and exclusion. $\endgroup$
    – Nicholas
    Nov 12, 2015 at 15:24

1 Answer 1


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$ Nov 12, 2015 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$ Nov 12, 2015 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.