Practice By Tag: The Principle of Inclusion and Exclusion

Question: 2015 Fall Final - 3

1 . How many bitstrings $s_1s_2 \dots s_{20}$ of length 20 have the property that $s_1s_2s_3 = 000$ or $s_2s_3s_4 = 000$?

(a)

$2^{18} - 2^{16}$

(b)

$2^{17} - 2^{16}$

(c)

$2^{18} - 2^{17}$

(d)

$2^{17} - 2^{15}$