# How many bit strings of length 7 begin with a 10 or end with 01?

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?

• There is overlap, which you have to subtract.
– user208649
Commented Sep 20, 2020 at 2:10
• Got it. Thanks! @TokenToucan
– user826944
Commented Sep 20, 2020 at 2:23
• Just note that I've modified the answer after you have accepted it, I've realized you were asking for OR, and not AND (as in my original answer).
– Sil
Commented Sep 20, 2020 at 7:32
• You may want to learn about principle of inclusion/exclusion. Commented Sep 20, 2020 at 7:33

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.