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..
Best Answer
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