A bit string is a finite sequence of the numbers 0 and 1. Suppose we have a bit string of length 7 that starts with 10 or ends with 01, how many total possible bit strings do we have?
I am thinking for the strings that start with 10, we would have 7−2=5 bits to choose, so 32 possible bit strings of length 7 that starts with 10. And for the strings that ends with 01, we would have 7-2=5 bits to choose, 32 possible bit strings to choose.
Can I just add the total from the two cases mentioned above together? Or is there any other case that I didn't consider?
Best Answer
If you want to count all cases that have starting digits $10$ OR ending digits $01$, then you would be overcounting (for example $1000001$ would be accounted for twice). In set notation, you would be doing $|A \cup B|=|A|+|B|$, which is not generally true (unless their intersection is empty). Instead, we have $|A \cup B|=|A|+|B|-|A \cap B|$, so you want to remove the overlapping cases. The overlapping cases look like $10xxx01$, so $2^3=8$ cases to subtract.
Basically you have run into a simple example of the inclusion–exclusion principle.