Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
    
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 at 22:27
1  
@vadim123: Ah, so the answer would be like $$2^7 + 2^4$$ I think? –  Zol Tun Kul Jun 1 at 22:27
2  
@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 at 22:34

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.