# How many bit strings of length 8 start with “1” or end with “01”?

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?

• 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. – stochasticboy321 Jun 14 '16 at 0:44
• Possible duplicate of How many bit strings of length 8 start with 00 or end with 1? – Did Jul 12 '16 at 15:40

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$.

• 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? – taylor.tackett Jun 14 '16 at 2:55
• 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|$. – André Nicolas Jun 14 '16 at 3:00
• i.e. 160 bit strings. – Lightness Races in Orbit Jun 14 '16 at 11:46

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.

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$$

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.