1

So the problem is to find how many 11-bit strings will have no consecutive three zeroes.

I have used recurrence to solve this problem. I set $T(n)$ to be the number of strings of size n that there will be no consecutive three zeroes. If the firsst digit is filled with 1, then you get $T(n-1)$ that can be filled and then you get $T(n-2) and T(n-3)$ for the second and third boxes.

T1- 2 (can be either 0 or 1) T2 - 4 (00,01,10,100) T3 - 7 (991,010,011,100,101,110, 111)

Now is when I start adding up the previous three terms up T4 = T1+T2+T3 = 13

T5 = T2+T3+T4 = 24

I keep doing this unitl I get to T11

T11 - T10 + T9+ t8 = 927 11 bit strings with no consecutive three 0s in a row

Noob Coder
  • 11
  • The total number of 11-bit strings is $2^{11}$. Now, consider the ones that contains "000", We can count strings that has "000" by thinking of "000" as one bit a 9-bit string. Does this help? – user614287 Nov 19 '18 at 10:16
  • @mathnoob - that approach is full of pitfalls, and ends up much more complicated than the approach in the question. Try that approach with n=4 or n=5, for example. Accounting for all the double-counting is way more complicated than this approach. – Daniel Martin Nov 19 '18 at 10:40
  • A similar problem (not a duplicate), with solution, can be found here: https://math.stackexchange.com/questions/3001026/a-coin-is-tossed-7-times-the-probability-that-at-least-4-consecutive-heads-appe/3001265#3001265 – awkward Nov 19 '18 at 15:50

0 Answers0