This is a problem from my Rosen's discrete math textbook in the Inclusion-Exclusion principle section. I'm asked to count how many 8-bit strings there are which don't contain 6 consecutive 0s. I'm not sure what I did wrong, but here's my approach:
Let $A$ be the set of bit strings of the form 000000**
Let $B$ be the set of bit strings of the form *000000*
Let $C$ be the set of bit strings of the form **000000
(Note: intentionally did not format the 0s and stars above so they line up nicely).
Okay, so here's what I know:
By permutation, $|A| = |B| = |C| = 4$
Looking at the overlaps, I've concluded that:
$|A \cap B| = 5$
$|A \cap C| = 4$
$|B \cap C| = 5$
$|A \cap B \cap C| = 4$
By the formula, the set of bit strings that contain 6 consecutive 0s is of size:
$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| = 4 + 4 + 4 - 5 - 4 - 5 + 4 = 12 - 10 = 2$
Calculating the total number of possible 8-bit strings with no restrictions, I get $2^8$. Subtracting the above value from this gives $2^8 - 2$ 8-bit strings without 6 consecutive 0s.
What did I do wrong?
$|A\cap B|$ are those of both $000000**$ and of the form $*000000*$ which mean the first and seventh terms are $0$ so they are of the form $0000000*$ and there are $2$ of them.
So $|A \cap B| = 2\ne 5$
$A\cap C$ are all those of the form $000000**$ and also of the form $**000000$ which means all terms are of the form $00000000$ and there is only one such.
So $|A\cap C| = 1\ne 4$
And likewise $B\cap C$ or those of the form $**000000$ and $*000000*$ so of the for $*0000000$ and there are two of them
So $|B\cap C| = 2\ne 5$.
An $|A\cap B \cap C| $ mean that are of the form $**000000, *000000*,000000**$ so all terms are $0$. So there are $1$ of them.
So $|A\cap B\cap C| = 1$.
So there are with 6 or more consective $0$: $4 + 4+ 4 - 2-1-2+1 = 8$ such strings. So there are $2^8 - 8$ that don't.
The eight are
$00000000$ that one is in all $A$,$B$ and $C$.
$00000011,0000010$ those two are in $A$ only.
$00000001$ that one is in $A$ and $B$.
$1000001$ that one is in $B$ only.
$1000000$ that one is in $B$ and $C$
and $11000000, 01000000$ are in $C$ only.