Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 8 '13 at 4:14
    
@rossmilikan edited. as u can see, there's no S0 -> so, S1 is the init, S1 = 1. S2 = 1 + 3 =4 –  user1988385 Mar 8 '13 at 4: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 8 '13 at 4: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 8 '13 at 4:35
add comment

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.