Let $W(c,n)$ denote the number of words of length $c$ from an alphabet of $n$ letters. Then $W(c,n)=n^c$.
Out of these, the number of words of the same size that do not contain one of the letters is $W(c,n-1)=(n-1)^c$. The number of ways of choosing which letter is missing is $\binom{n}{1}$.
The number of words of the same size that do not contain two letters is $W(c,n-2)=(n-2)^c$. The number of ways of choosing which two letters are missing is $\binom{n}{2}$... and so on ...
Now we use inclusion-exclusion principle: (subtract the number of words missing one of the letters, then add the number missing two of the letters, subtract the number missing three of the letters,...)
We get:
$$W(c,n)-\binom{n}{1}W(c,n-1)+\binom{n}{2}W(c,n-2)-\binom{n}{3}W(c,n-3)+\cdots+(-1)^{n-1}\binom{n}{n-1}W(c,n-(n-1)).$$
This is
$$n^c-\binom{n}{1}(n-1)^c+\binom{n}{2}(n-2)^c-\binom{n}{3}(n-3)^c+\cdots+(-1)^{n-1}\binom{n}{n-1}1^c.$$
or
$$\sum_{k=0}^{n-1}(-1)^k\binom{n}{k}(n-k)^c.$$
Another way could be: Denote $S_c^n$ the number of ways to partition the word of length $c$ into $n$ pieces. Then we just need to choose which letter goes to each of the $n$ pieces. This number is $n!$. So the number of words we are looking for is
$$n!S_c^n.$$
The numbers $S_c^n$ are called Stirling's numbers of the second kind.
Lets use inclusion-exclusion method.
First we find the number of bit-strings from size of $n$ that doesn't contain the sequence '000'. We will construct recursion formula, let $F(n)$ be that number.
- If the first bit is '1' then the rest is just a string that doesnt contain '000' from size $n-1$
- If the first bits is '01' then the rest is just a string that doesnt contain '000' from size $n-2$
- If the first bit is '001' then the rest is just a string that doesnt contain '000' from size $n-2$
Therfore we get:
$F(n) = F(n-1)+F(n-2)+F(n-3)$
With the initial conditions
$F(0) =1, F(1) =2, F(2) =2^2$
With te same method we get:
$G(n) = G(n-1)+G(n-2)+G(n-3)+G(n-4)$
With the initial conditions
$G(0) =1, G(1) =2, G(2) =2^2, G(3)=2^3$
Where $G(n)$ is the number of bit-strings from size of $n$ that doesn't contain the sequence '1111'.
Now, by opening the recursion up we get $F(8)= 149$ and $G(8)=208$
So if we define:
- A = bit-string of size 8 that contain '000'
- B = bit-string of size 8 that contain '1111'
and by what we calculated we have $|A| = 2^8-F(8)$ and $|B| = 2^8-G(8)$
What left to complete inclusion exclusion is to find the size of $|A\cap B|$, which is easy since the only strings that satisfy both are:
'00001111' , '11110000', '11111000', '00011111', '00011110', '10001111', '01111000', '11110001'
Now the desiered number is $|A|+|B|-|A \cap B|$
Best Answer
To count the number of 8-bit strings that have exactly 3 zeros and at least 2 are adjacent, you can count the number of 8 bit strings with exactly 3 zeros, and subtract those in which they are not adjacent.
The number of 8-bit strings with exactly 3 zeros is $\binom{8}{3}$. To count those with no two zeros adjacent, consider placing the five $1$s, leaving space between them for possibly adding a $0$: $$\Box \quad1\quad \Box\quad 1 \quad\Box \quad 1 \quad \Box\quad 1 \quad \Box \quad 1\quad \Box$$ Now you will select three of the six boxes to place a zero in. There are $\binom{6}{3}$ ways of doing this. So the number of $8$-bit strings with exactly $3$ zeros, and at least two zeros adjacent is $$\binom{8}{3} - \binom{6}{3} = 56 - 20 = 36.$$
I don't know how you counted for $4$. Doing the same thing as above, there are $\binom{8}{4}$ strings with exactly four $0$s; if you place all the $1$s first, there are five places where a zero may go, so you need to subtract $\binom{5}{4}$ strings that have no two zeros adjacent; that gives $\binom{8}{4}-5 = 65$ strings.
The rest seem okay.
Using these totals, we have: $0 + 7 + 36 + 65+ 56+28+8+1=201$ total.