1
$\begingroup$

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?

$\endgroup$
4
  • 4
    $\begingroup$ There is overlap, which you have to subtract. $\endgroup$
    – user208649
    Commented Sep 20, 2020 at 2:10
  • $\begingroup$ Got it. Thanks! @TokenToucan $\endgroup$
    – user826944
    Commented Sep 20, 2020 at 2:23
  • $\begingroup$ 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). $\endgroup$
    – Sil
    Commented Sep 20, 2020 at 7:32
  • 1
    $\begingroup$ You may want to learn about principle of inclusion/exclusion. $\endgroup$
    – K.defaoite
    Commented Sep 20, 2020 at 7:33

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.