# How many bit strings of length $8$ start with $00$ or end with $1?$

How many bit strings of length $8$ start with $00$ or end with $1$?

I know about product rule and sum rule but I'm unsure how to incorporate it into this.

Would it be like this$? (x$ being either $1$ or $0):$

For starting with $00:$ $0 0 x x x x x x$

• $2^6$ combinations?

For ending with $1:$ $x x x x x x x 1$

• $2^7$ combinations?
• You need to describe those strings that have both properties; it might help you to think of the Venn diagram. – András Salamon Apr 22 '13 at 16:30

Yes, you are correct about each separate case, but to find the number of bit strings of length $8$ that either start with two zeros or end in a one (or both), we cannot simply *add* the two counts and say "we're done." We can use the sum rule, but with modifications:

If we add the counts $2^6 + 2^7$, we need to also account for having double counted those bit strings which both start with two zeros and end in a one: Subtract that number of strings from the sum, and you'll have your answer.

Clarification: The number of bit strings of length 8 of the form 0 0 x x x x x 1 will have been counted $(1)$ in the first total of all strings of the form 0 0 x x x x x x, and $(2)$ it will have been counted in the second total of all strings of the form x x x x x x x 1. So we need to subtract the number of strings of the form 0 0 x x x x x 1 from the combination of the first count and second count, so that they are only counted once.

So, we count the number of bit strings of the form: 0 0 x x x x x 1,

and just as you computed the first two counts, we see that there are $2^5$ such strings which have been counted twice, so we will subtract that from the sum of the first two counts.

Total number of bit strings that start with two zeros $(2^6)$ or end in a one $(2^7)$ or both ($2^5$):

$$2^6 + 2^7 - 2^5$$

• But the question says "How many bit strings of length 8 start with 00 OR end with 1?" Emphasize the "or". In that case, is finding the number of the combinations of 00xxxxx1 still the right answer? – user1766555 Apr 22 '13 at 16:34
• Yes...we are using the inclusive sense of "or", that means one or the other or both. – amWhy Apr 22 '13 at 16:39
• 00xxxxx1 will have been counted in the first total, and it will have been counted in the second total. So we need to subtract the number of strings of that form from the combination of the first count and second count. – amWhy Apr 22 '13 at 16:41
• I think it looks like a word problem Amy. – Mikasa Apr 22 '13 at 18:41
• @amWhy: Nice answer +1 – Amzoti Apr 23 '13 at 0:11

As @AndrásSalamon says, you need to check how many of them verify both properties.

I'll give you a hint. Start by saying that:

• all the strings starting with $00$ form the set $A$.
• The strings which end with $1$ form the set $B$.

Your question is basically how many elements are in $A\cup B$.

The only thing you need to know is:

$$\#(A\cup B)=\#(A)+\#(B)-\#(A\cap B)$$

Or in logic terms:

$$nb(A\space\mbox{or}\space B)=nb(A)+nb(B)-nb(A\space\mbox{and}\space B)$$

where $\#(X)$ denotes the number of elements in the set $X$.

Check out this image for better understanding of what $A$,$B$,$A\cup B$ and $A\cap B$ are:

It's now easy to understand the formula: The red part is counted in both $A$ and $B$ so if you add the number of elements in $A$ and those in $B$ you have the yellow set plus an additional red set. If you substract one red set ($A$ and $B$) from this, you get your yellow set ($A$ or $B$).

Do you see how to go with your problem now ?

Edit: In other words, $A\cup B$ means $A$ or $B$ (or both) and $A\cap B$ means $A$ and $B$ ;)

• Thank you for illustration :) – user1766555 Apr 22 '13 at 16:50
• You're welcome ! Hope it made it clearer how you could find the formulas yourself if you need them again ;) – Dolma Apr 22 '13 at 16:53