1
$\begingroup$

Count the number of bit strings that start with four $0$'s or end with three $1$'s if the length of the bit string is:

  1. $7$
  2. $4$
$\endgroup$
2
$\begingroup$
  1. For 4 the only options are "0000" , "0111" and "1111".

  2. For 7 use inclusion exclusion principle, with event $A$ as getting four zeros in front and event $B$ as 3 one's in the end. So answer will come out to be $2^3+2^4-1$.

In general for lengths $n>=7$ the answer would be $2^{n-4}+2^{n-3}-2^{n-7}$.

$\endgroup$
8
  • 1
    $\begingroup$ 2. is even simpler to count than using the inclusion exclusion principle. A matching string either starts with 0000 or not. If it doesn't it must end in 111. There are $2^3$ of the first, $2^4-1$ of the second. $\endgroup$ – copper.hat Feb 16 '15 at 18:18
  • $\begingroup$ yeah you are correct $\endgroup$ – sashas Feb 16 '15 at 18:19
  • $\begingroup$ how come you subtract 1? $\endgroup$ – Csci319 Feb 16 '15 at 18:49
  • $\begingroup$ because the string "0000111" gets counted twice once in event A and once in B , 1 is the cardinality of intersection of A and B and thus is subtracted $\endgroup$ – sashas Feb 16 '15 at 18:51
  • $\begingroup$ @sasha if the length is 8 would the answer be $2^4+2^5-1?$ $\endgroup$ – Csci319 Feb 19 '15 at 21:35

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.