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$.


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$.

  • $\begingroup$ I've tried use combinatorics to determine how many string containt this substring and then subtract. $\endgroup$ – Ondrej Janacek Nov 28 '11 at 20:09
  • $\begingroup$ Please edit your question to show some of this work, and some thoughts about how that would have led to a recurrence relation. $\endgroup$ – hmakholm left over Monica Nov 28 '11 at 20:12
  • $\begingroup$ Ok, check my question again, it is edited. $\endgroup$ – Ondrej Janacek Nov 28 '11 at 20:24

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.

| cite | improve this answer | |
  • $\begingroup$ +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? $\endgroup$ – msh210 Nov 30 '11 at 18:18
  • $\begingroup$ @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}$. $\endgroup$ – Gerry Myerson Dec 1 '11 at 5:53

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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – msh210 Nov 28 '11 at 20:11
  • $\begingroup$ I do not need help with homework, I just missed last seminar and I have absolutely no idea, how to solve problem like this. $\endgroup$ – Ondrej Janacek Nov 28 '11 at 20:14
  • $\begingroup$ @Andrew: Like I said: the OEIS comment indicates how to do so. $\endgroup$ – msh210 Nov 28 '11 at 20:16
  • $\begingroup$ I think there should be easier solution. Still, it is first example from seminar. Second is much more complicated. $\endgroup$ – Ondrej Janacek Nov 28 '11 at 20:37

It is easier to set up computing the number of strings that do contain $010$, and subtract from $2^n$, the total.

To do the above, you have four cases: Strings that already contain $010$, can extend them in any way; strings that don't contain $010$ are of three types: need to add $010$, adding $1$ have one of the same; end in $0$, still require $10$ (add $0$, get one of these); end in $01$, need $0$ (add $1$, you are back at the "still missing $010$" case). So you can set up a system of recurrences and solve.

Computer Science types will recognize this as the construction of a deterministic finite automaton.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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