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.

Let $S_n$ be the number of binary strings of length = $n$ which do not contain the sub-string $010$.

Find a recurrence relation for $S_n$.

edit:

I tried for $n=4$. There are two positions in string, how to place $010$.

[]010 or 010[] ... so last place is choosen from 2 possible numbers -> $2^1$ and multiplied by $2!$ because of permutation of two items.

Number of all strings is $2^4$. Number of string with $010$ for $n=4$ is $2^1*2! = 4$. Result is 12 strings doesn't containt substring.

It is ok for $n=3$ but failed for $n=5$.

share|improve this question
1  
What have you tried? –  Henning Makholm Nov 28 '11 at 19:59
    
I've tried use combinatorics to determine how many string containt this substring and then subtract. –  Ondrej Janacek Nov 28 '11 at 20:09
    
Please edit your question to show some of this work, and some thoughts about how that would have led to a recurrence relation. –  Henning Makholm Nov 28 '11 at 20:12
    
Ok, check my question again, it is edited. –  Ondrej Janacek Nov 28 '11 at 20:24
add comment

2 Answers

up vote 2 down vote accepted

The comment at the OEIS entry looks pretty easy to me. Maybe this is a tiny bit simpler.

Any such string must end in exactly one of the following: 1; 110; 1100; 11000; etc.

So $$a_n=a_{n-1}+a_{n-3}+a_{n-4}+a_{n-5}+\cdots$$

Now replace $n$ everywhere with $n-1$, and subtract the new equation from the old one.

EDIT: Maybe I should expand on this somewhat.

Suppose we have a string of length $n$ with no 010. It could end in 1. In that case, it's a string of length $n-1$ with no 010, with a 1 tacked on at the end. There are $a_{n-1}$ such things.

Or, it could end in a 0. In that case, it might end in any number of zeros. If it isn't all zeros, then it ends in a 1 followed by those ending zeros, and it can't end in 01 followed by those zeros (since that would give a 010), so it must end in 11 then zeros; it must end in 110, or 1100, or 11000, etc., etc.

If it ends in 110, it's a sequence of length $n-3$ with no 010, with 110 tacked on at the end; the number of these is $a_{n-3}$.

If it ends in 1100, it's a sequence of length $n-4$ with no 010, with 1100 tacked on at the end; there are $a_{n-4}$ of these.

And so on. So we get $$a_n=a_{n-1}+a_{n-3}+a_{n-4}+a_{n-5}+\cdots$$

But $n$ is arbitrary. Replacing it with $n-1$ everywhere, we get $$a_{n-1}=a_{n-2}+a_{n-4}+a_{n-5}+a_{n-6}+\cdots$$

Now subtracting the last equation from the one before, we get $$a_n-a_{n-1}=a_{n-1}-a_{n-2}+a_{n-3}$$ All the other terms cancel. So we are left with the recurrence, $$a_n=2a_{n-1}-a_{n-2}+a_{n-3}$$

Let's check it. It's easy to see $a_1=2,a_2=4,a_3=7$. Also, $a_4=12$, because there are 16 strings of length 4 of which we must omit 4, namely, 0100, 0101, 0010, and 1010. Putting $n=4$ into the formula yields $$12=(2)(7)-4+2$$ which is correct, so maybe the answer is right.

share|improve this answer
    
+1. You omitted the case it's all $0$s. This adds $1$ to each of $a_n$ and $a_{n-1}$, which then cancel, yielding the same result. You also omitted the case the string is $100$: how to deal with that? –  msh210 Nov 30 '11 at 18:18
    
@msh210, you are right, I have been careless. For every $n$, there is the string of $n$ zeros, and also the string with a 1 followed by $n-1$ zeros. So it should be $a_n=2+a_{n-1}+a_{n-3}+\cdots$ (except when $n=1$; then $a_1=1+a_0$), but as in your comment the $+2$ cancels when we do $a_n-a_{n-1}$. –  Gerry Myerson Dec 1 '11 at 5:53
add comment

From http://oeis.org/A000253:

$a_n = 2a_{n-1}-a_{n-2}+a_{n-3}+2^{n-1}$

...

number of binary strings of length $n+2$ containing the pattern $010$

And subtract.

share|improve this answer
    
This answer assumes the asker is actually seeking a recurrence relation: it provides one. If, OTOH, the asker is actually seeking help with homework (as I suspect), then he'll (presumably) need to explain why the recurrence relation holds. In that case, he can check the proof in the OEIS comment. –  msh210 Nov 28 '11 at 20:11
    
I do not need help with homework, I just missed last seminar and I have absolutely no idea, how to solve problem like this. –  Ondrej Janacek Nov 28 '11 at 20:14
    
@Andrew: Like I said: the OEIS comment indicates how to do so. –  msh210 Nov 28 '11 at 20:16
    
I think there should be easier solution. Still, it is first example from seminar. Second is much more complicated. –  Ondrej Janacek Nov 28 '11 at 20:37
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.