0

So I got this problem: compute the number of n bit string that do not contain pattern 010 that have no leading 0, one leading zero, two leading zero, and so on.

So far, I got the expression: 

Sn = Sn-1 + Sn-3 + Sn-4...+ S1

However the solution is:

Sn = Sn-1 + Sn-3 + Sn-4...+ S1 + 3

My question is, where + 3 come from? thx

update: I was thinking that if the string that does not contain 010 begin w/ 1, the rest will be Sn-1. if the string begin with one 0 (which mean the first two bit is 01), the next bit have to be 0 -> Sn-3 and so on

user1988385
  • 281
  • It would help to see how you got your answer. It is easier to check that way. Clearly it is not right as S1=2 and S2 can't be 5-there aren't that many strings. But S2 is 4, and your recurrence would make it 2 – Ross Millikan Mar 08 '13 at 04:14
  • @rossmilikan edited. as u can see, there's no S0 -> so, S1 is the init, S1 = 1. S2 = 1 + 3 =4 – user1988385 Mar 08 '13 at 04:26
  • I'm not understanding your definition of Sn. It seems both $0$ and $1$ are legal one bit strings, so S1 should be 2, and all four two bit strings are still legal, so S2 should be 4. – Ross Millikan Mar 08 '13 at 04:32
  • if n=0, there's no string at all. which mean the number of occurrence of a string that not contain 010 is 0. Honestly, I don't rly get this problem too :D – user1988385 Mar 08 '13 at 04:35

1 Answers1

0

Let us define $00(n)$ as the number of n bit strings that start with $00$ and do not include $010$, and $10(n), 01(n),$ and $11(n)$ similarly. Then $S(n)$ the total number of $n$ bit strings is the sum of these. We then have $$00(2)=10(2)=01(2)=11(2)=1\\00(n)=01(n-1)+00(n-1)\\01(n)=11(n-1)\\10(n)=00(n-1)+01(n-1)\\11(n)=10(n-1)+11(n-1)$$ It is curious (and easy to prove) that $11(n)=S(n-2)$. The recurrence should be solvable by diagonalizing the matrix. The growth rate is the square of the plastic constant, about $1.754877666$ It is also the real root of $x^3-2x^2+x-1=0$

Added: It starts $1,2,4,7,12,21,37,65,114,200,351. This is OEIS A005251 where there is more description.

Ross Millikan
  • 374,822