11
$\begingroup$

A bit string is a finite sequence of the numbers $0$ and $1$. Suppose we have a bit string of length $8$ that starts with a $1$ or ends with an $01$, how many total possible bit strings do we have?

I am thinking for the strings that start with a 1, we would have $8 - 1 = 7$ bits to choose, so $2^7$ possible bit strings of length $8$ that starts with a $1$?

Can I go about the second condition the same way and just add the total's together? That is, if my logic is even correct in the first place?

$\endgroup$
  • 4
    $\begingroup$ You can use the idea you had to figure out the number of strings with a $01$ at the end, but you'll be over-counting if you simply sum the two numbers since there will strings which start with $1$ and end with $01$, and you'll be counting each of these twice. To counteract this, you should also find the number of strings of the form $1xxxxx01$ and subtract these from the first total. This is known as the inclusion-exclusion principle. $\endgroup$ – stochasticboy321 Jun 14 '16 at 0:44
  • $\begingroup$ Possible duplicate of How many bit strings of length 8 start with 00 or end with 1? $\endgroup$ – Did Jul 12 '16 at 15:40
16
$\begingroup$

We interpret starts with $1$ or ends in $01$ as meaning that bit strings that satisfy both conditions qualify.

By your correct analysis, there are $2^7$ bit strings that start with $1$.

Similarly, there are $2^6$ bit strings that end with $01$.

The sum $2^7+2^6$ double-counts the bit strings that start with $1$ and end with $01$.

There are $2^5$ of these, so there are $2^7+2^6-2^5$ bit strings that start with $1$ or end with $01$.

$\endgroup$
  • $\begingroup$ Thank you for making it clear and confirming my original thought process. I felt like there would be some extra's in there; would these 'extras' also be found similarly by taking the intersection of the two if they were sets? $\endgroup$ – taylor.tackett Jun 14 '16 at 2:55
  • 1
    $\begingroup$ You are welcome. I deliberately avoided formulas. But for any finite set $X$, let $|X|$ be the number of elements in $X$. Let $A$ be the set of strings that begin with $1$, and let $B$ be the set of strings that end in $01$. The set we want to count is $A\cup B$, so we want $|A\cup B|$. We have in general $|A\cup B|=|A|+|B|-|A\cap B|$. The $2^5$ that I subtracted at the end is $|A\cap B|$. $\endgroup$ – André Nicolas Jun 14 '16 at 3:00
  • $\begingroup$ i.e. 160 bit strings. $\endgroup$ – Lightness Races in Orbit Jun 14 '16 at 11:46
4
$\begingroup$

The strategy you seem to be proposing is to note that there are $2^7$ bit strings starting with $1$ and $2^6$ ending with $01$, since one may make $7$ choices in the first case and $6$ choices in the second. If we add these up to get $2^6+2^7$, this doesn't quite work to count the number of strings satisfying either condition. In particular, consider a string like $$10000001$$ it both starts with $1$ and ends with $01$, so the above method would have counted it twice. In particular, the remedy for this is to subtract out the number of strings that satisfy both conditions from the sum $2^6+2^7$ to compensate for counting those strings twice.

This is the inclusion-exclusion principle.

$\endgroup$
3
$\begingroup$

Here is another way to arrive at the answer, without doing the whole "double count and then correct for it" dance:

Of all possible octets (8-bit strings), half of them will begin with $1$. Of the other half (i.e. those that begin with $0$), a quarter will end with $01$. Since there are $2^8$ possible octets, we have: $$ 2^8 \times \frac{1}{2} + 2^8 \times \frac{1}{2} \times \frac{1}{4} \\ 2^7 + 2^5 $$ While this may not look identical to the other answers, note that: $$ 2^5 = 2^6 - 2^5 $$ because $$ 2^6 - 2^5 = 2 \times 2^5 - 2^5 = 2^5 + 2^5 - 2^5 = 2^5 $$

$\endgroup$
1
$\begingroup$

Although the other answers show you how to work your logic into a correct application of the inclusion-exclusion principle, one could take a slightly different approach and sum sizes of nonintersecting sets of events.

Case 1:

First binary digit is 1. Given this condition, all possible strings with attribute fulfill the required 'Or' condition. So there are $2^7$ strings in this set.

Case 2:

The first binary digit is 0. Given this condition, only strings that end in $01$ fulfill the required condition. This leaves only 5 binary digits to freely choose: we count all of the form $0xxxxx01$. So there are $2^5$ strings in this set.

Summing the number of combinations for the two mutually exclusive, but exhaustive conditions yields $2^7 + 2^5$ combinations.

$\endgroup$

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.