I'm not sure how to use inclusion-exclusion to calculate the number of bit strings of length 9 that either begin with two 0s, have eight consecutive 0s, or end with a 1 bit.
Here is what I have done which helps me see the number of possibilities:
Condition 1: Beginning with two 0's leaves me with the rest of the position being equal to $2^{7}$ = 128
Condition 2: Eight consecutive 0's leaves me with these 3 possible combinations:
$0 0 0 0 0 0 0 0 0$
$1 0 0 0 0 0 0 0 0$
$0 0 0 0 0 0 0 0 1$
Condition 3: Ending with one bit; Since the positions can have either 1 or 0, and there are 128 possible ways that the 1's and 0's can be placed to fit the length of 9, I divided 128/2 and got that there are 64 possibilities for the last bit to be 1.
I know that the formula for inclusion-exclusion is: |A ∪ B ∪ C| = (|A| + |B| + |C|) - (|A ∩ B| + |A ∩ C| + |B ∩ C|) + |A ∩ B ∩ C|
I'm just not sure how to involve the logic I used to get the bolded values above with this formula. Thank you in advance!!
$A$ is number of ways of two starting bits as zeroes.
$B$ is number of ways for at least $8$ consecutive zeroes.
$C$ is number of ways of ending bit as $1$.
$A = 2^7 = 128$ as you identified.
$B = 3$ as you identified.
$C = 2^8 = 256$ (not $64$, if I understand this point correctly)
Now,
$A \cap B = 2$ (out of $3$ cases of $B$, one of them does not have first two bits as zeroes, two of them have).
$B \cap C = 1$ (out of 3 cases of $B$, one of them has last bit as $1$)
$A \cap C = 2^6 = 64$ (First two bits are fixed and so is the last bit. There are choices only for $6$ bits in between).
$A \cap B \cap C = 1$
So your answer should become $128 + 3 + 256 - 2 - 1 - 64 + 1 = 321$.