How many different $ 8$ bit strings begin with $000$, end with $001$, or have $10$ as the $4th$ and $5th$ bits, respectively?

Question

I keep obtaining $127$ as my final answer yet I know this is incorrect. I start with the # of combinations for $8$ bit strings that begin with $000$, which is $2^5$. Then calculate the # of $8$ bit strings that end with $001$, which is also $2^5$, then attempt to calculate the # of $8$ bit strings that have $1$0 as the $4$th and $5$th bits (this is where I think I am messing up), which I get as $2^6$. $2^5 + 2^5 + 2^6 = 128$, but I know we must subtract the case where a string has all three of these conditions, of which there is only 1 (a string that looks like $00010001$). I therefore obtain $128-1 = 127$, yet this is incorrect. Any ideas?

Answer 1

If $A$ is set of all strings starting with $000$,

$B$ is set of all strings ending with $001$ and,

$C$ is set of all strings with $4$th and $5$th places being $10$

Then,

$|A| = |B| = 2^5, |C| = 2^6$

$|A \cap B| = 2^2, |B \cap C| = |A \cap C| = 2^3$

$|A \cap B \cap C| = 1$

So your answer should be

$ = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$

$= 109$

Answer 2

Let's do this step by step. As you correctly noted, there are $2^5$ strings that begin with $000$, and $2^5$ strings that end in $001$. The key is to correctly count how many we counted twice. In other words we're looking for all strings of the form $000xx001$ -- but the $x$'s could be anything, so there are $2^2$ of those. This gives us a partial total of $2^5 + 2^5 - 2^2$. Next we're looking at all strings of the form $xxx10xxx$. As before, there are $2^6$ of those but we need to know how many we counted twice, i.e. subtract all strings of the form $00010xxx$ and $xxx10001$. There are $2^3 + 2^3$ but we must take care here: there is in fact a single string, $00010001$, that we're subtracting twice because it satisfies both formats. So the expression becomes: $$(2^5+2^5-2^2)+(2^6-2\cdot2^3+1).$$ I leave it to you to compute the total.

P.S. As InterstellarProbe notes in the comments, and if you're familiar with set theory, the procedures above may be formalised (as far as event spaces go) with the following principle: $$\#\left(A \cup B \cup C\right) = \#A + \#B + \#C - \#(A\cap B) - \#(A\cap C) - \#(B\cap C) + \#(A\cap B\cap C)$$

Answer 3

To avoid the inclusion-exclusion principle, we can count the complement.

If an $8$-bit string does not begin with $000$, does not end in $001$, and does not have $01$ as its $4^{\text{th}}$ and $5^{\text{th}}$ bits, then there are $2^3-1 = 7$ possibilities for the first three bits, $2^2-1 = 3$ possibilities for the next two bits, and $2^3-1=7$ possibilities for the last two.

Therefore there are $7 \cdot 3 \cdot 7 = 147$ strings that don't satisfy the condition, and $2^8 - 147 = 109$ strings that do.

Answer 4

Another approach (which is kind of fun I think) is to count the number of string that don't have any of the three properties.

For $8$ it strings, there are $2^8=256$ possibilities.

Now - to count the strings that don't have any of these properties:

• For the first three bits, there are 7 possibilities (2^3=8 except for 000)
• For the next two, there are 3 possibilities (2^2-4 except for 01)
• For the lat three, there are again 7 possibilities

So, overall there are $7 \times 3 \times 4 = 147$ strings that don't have any of the three criteria which leaves $256 - 147 = 109$ that have at least one.