Counting when there are two inclusive conditions.

How many 8-bit sequences begin with $101$ OR (inclusive) have a $1$ as their fourth bit?

For the first condition, we need only to decide the values of the $5$ other bits, so there are

$$2^5$$

sequences starting with $101$.

For the second condition, we have to decide the values of the other $7$ bits, so there are

$$2^7$$

sequences with a $1$ as their fourth bit.

The final answer, however, surely cannot be

$$2^5+2^7$$

Because $2^5$ includes some scenarios with a $1$ as the fourth digit, whereas $2^7$ includes cases with a $101$ at the beginning, so I would be over-counting this. What do I do in this case?

-
This doesn't really help though, because he's derived this principle himself, but doesn't know how to calculate the intersection of the two sets. – recursive recursion Jun 1 '14 at 22:27
@vadim123: Ah, so the answer would be like $$2^7 + 2^4$$ I think? – Zol Tun Kul Jun 1 '14 at 22:27
@Omega subtract the number of "intersections". i.e, see how many 8-bits start with 101 and have 1 as their fourth bit – Fermat Jun 1 '14 at 22:34

The big problem here: if $A_1$ is the set of sequences which satisfy the first property and $A_2$ is the set of sequences which satisfy the second, then (exactly as you suggest), $\lvert A_1\rvert+\lvert A_2\rvert$ over-counts.

However, it over-counts in a very predictable way: namely, any sequence which is in exactly one of the sets is counted only once, while any sequence in $A_1\cap A_2$ is counted twice! So, this tells us that $$\lvert A_1\rvert+\lvert A_2\rvert=\lvert A_1\cup A_2\rvert+\lvert A_1\cap A_2\rvert.$$ But, we can rearrange this to get $$\lvert A_1\cup A_2\rvert=\lvert A_1\rvert+\lvert A_2\rvert-\lvert A_1\cap A_2\rvert.$$ So, you need only compute $\lvert A_1\cap A_2\rvert$ -- that is, the number of sequences which satisfy BOTH properties -- and subtract it from your previous total.

(This is actually the most basic form of a more general process called the inclusion-exclusion principle.)

-

I think the easiest method here is to take the total of all 8-bit sequences and subtract those that don't meet the requirement: those that do not begin with $101$ AND do have a $0$ as their fourth bit.

There are $7$ choices for the first $3$ bits, $1$ choice for the fourth, and $2^4=16$ for the remaining bits. This gives an answer of

$$2^8-7(2^4)=16(2^4)-7(2^4)=9(2^4)$$

-