How can I find the recurrence relation with a) no block of 2 consecutive 0's and b)no block of 3 consecutive 0's.
Please help me understand this material, detailed explanation will be much appreciated, Thanks
Asked
Active
Viewed 465 times
1 Answers
1
We deal with no $3$ consecutive $0$. The same approach will work for no $2$ consecutive $0$, but is simpler.
Let $a_n$ be the number of binary strings of length $n$ with no $3$ consecutive $0$. Call such a string a good string. Let $n\gt 3$.
A good $n$-string with $n\gt 3$ can be of three types:
Type 1: ends in a $1$.
Type 2: ends in a single $0$
Type 3: ends in a double $0$.
Type 1: We can make a good $n$-string of Type 1 by appending a $1$ to a good $(n-1)$-string. And all Type 1 good $n$-strings are obtained in this way. Thus there are exactly as many good Type 1 $n$-strings as there are good $(n-1)$-strings. By definition there are $a_{n-1}$ of these.
Type 2: A good string of length $n\gt 3$ that ends in a single $0$ must end in $10$. So it is obtained from a good $(n-2)$-string by appending $10$ to it. So there are just as many good Type 2 $n$-strings as there are good $(n-2)$-strings. By definition there are $a_{n-2}$ of these.
Type 3: A good string of length $n\gt 3$ that ends in $00$ must end in $100$. So it is obtained from a good $(n-3)$-string by appending $100$ to it. So there are just as many good Type 3 $n$-strings as there are good $(n-3)$-strings. By definition there are $a_{n-3}$ of these.
It follows that if $n\gt 3$ then $$a_n=a_{n-1}+a_{n-2}+a_{n-3}.$$
André Nicolas
- 507,029
-
what about a Type 4, ending with double 1's? – Roy Kesserwani May 10 '14 at 20:27
-
That ends in a $1$. Taken care of under Type 1. – André Nicolas May 10 '14 at 20:29
-
shouldn't n be n >= 3? – Roy Kesserwani May 10 '14 at 20:41
-
It could be taken as that. Then for $n=3$, Type 3 strings have shape $w100$ where $w$ is a good word of length $n-3=0$. That's OK, if we are comfortable with the empty word, which is good. So we can start indexing at $0$ and note that $a_0=1$. That makes things a little nicer from a (this) mathematician's point of view. But since you are relatively new at this, I decided not to bring in the empty word, and started with $a_1,a_2,a_3$ separately computed, and chose to deal in the recursion with $n\gt 3$. – André Nicolas May 10 '14 at 20:54