Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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$.
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.
