In how many bit strings of length 10 are there with no 3 0s adjacent

Question

it is hard for me dealing with more than 2 not adjacency problems, I need some straightforward approaches for these kinda problems, I have searched most of the community looking for similar problems but I got sorta more confused. it would be very nice of you to put me in the right direction. The title is my question A But for B: B)if at least 3 0s are not adjacent?

A) My notion is, 2 0's are allowed, So at first as we got only 3 0s to place in, I get the total by $10\choose3$ =$120$ And for 3 adjacent 0s: 0001111111,1000111111,1100011111,1110001111,1111000111,1111100011,1111110001,1111111000, indicating we have only 8 locations to place our consecutive 0s, subtracting this from the total , $120 - 8 = 112$ , was this a correct approach?

For B) it means we can place in more 0s than just 3 right? If so , non consequtive 3 0s,4 0s, ... , 10 0s Summing them all up we have 36, hence 120 - 36 = 84 . ? Help please..

Answer 1

For all who might come across my problem and would like to know about the combinatorial solution:

1. We start with 10 1s and 0 0. $10\choose0$ = 0

2. 9 1's, means we got 10 gaps to place one 0, $10\choose1$ = 10

3. 8 1's, we got 9 gaps left and we should choose 2 locations to place 0, $or$ choose one single location to place $00$ $9\choose2$ + $9\choose1 $

4. 7 1's, we got 8 gaps left and we should choose 3 locations to place 0, $or$ choose 2 locations to place 00 and 0, with $\frac{2!}{1!}$ ways for their arrangement. $8\choose3$ + $8\choose2 $ $\times$ $\frac{2!}{1!}$

5. The string includes 6 1's, leaving us with 7 gaps in between, either we should choose 4 locations to place 0, $or$ choose 3 locations to place 00 and 0,0 with $\frac{3!}{2!}$ ways for their arrangement.. $or$ 2 locations to place 00,00 $7\choose4$ + $7\choose3 $ $\times$ $\frac{3!}{3-1!}$ + $7\choose2$

6. The string includes 5 1's, leaving us with 6 gaps in between, either we should choose 5 locations to fill with 0's, $or$ choose 4 locations to place 00 and 0, 0, 0 with $\frac{4!}{3!}$ ways for their arrangement.. $or$ 3 locations to place 00,00 ,0 $6\choose5$ + $6\choose4 $ $\times$ $\frac{4!}{4-1!}$ + $6\choose3$ $\times$ $\frac{3}{3-1}$

7. The string includes 4 1's, leaving us with 5 gaps in between, either we should choose 5 locations to place 00,0,0,0,0 with $\frac{5!}{4!}$ ways for their arrangement $or$ choose 4 locations to place 00 and 00, 0, 0 with $\frac{4!}{2!2!}$ ways to arrange them. $or$ we can choose 3 locations to place 00,00 ,00 $5\choose5$ $\times$ $\frac{5!}{5-1!}$ + $5\choose4 $ $\times$ $\frac{4!}{4-2!4-2!}$ + $5\choose3$

8. The string includes 3 1's, leaving us with 4 gaps we should choose 4 locations to place 00,00,00,0 with $\frac{4!}{3!1!}$ ways for their arrangement $4\choose4$ $\times$ $\frac{4!}{3!1!}$

Summing them all up, we get 504...

Answer 2

if the question is "How many bitstrings of length 10 exist with three 0's, but non-adjacent?" Your solution to A. of 112 is right.

For B, you'd have to write a recurrence relation.

You can compose any acceptable string by combining $1, 01, 001$. The number of words you can create like this satisfies $w_n = w_{n-1} + w_{n-2} + w_{n-3}$. Since you can also finish with 0, 1, or 2 trailing 0's, you are interested in $w_8 +w_9 + w_{10}$ which happens to be $w_{11}$.

You have the tribonacci numbers, with an offset, so I think the answer is 504. http://oeis.org/A000073