\(\require{color}\)

Binary Strings No Triple 0’s

December 17th, 2016


Today we will look at a modified version of a thoroughly studied problem. Our problem is too determine the number of binary strings of length $n$ have no “000”, no triple 0’s. A very well studied problem is to find out how many binary strings of length $n$ there are that do not contain “00”, two zeros in a row. We will start by analyzing the latter, and then generalizing the solution. How can we accomplish this? The answer is the Fibonacci series, but the real question is why the answer is the Fibonacci series. Let’s dive in…

I. Derivation of the Series

We begin by looking at a picture. If we cannot have any “00”, we obviously cannot end in “00”. This means that our string must end in either “10” or “1”. If our string ended in a “0” without a “1” before it, we could possibly have a 0 as the 2nd to last character, and that would break the rule. Therefore, we know our string must end in “10” or “1”. Therefore, our string takes the following forms

$$\underbrace{\texttt{_ _ _ _ _ … _ _}}_{n-2}{\color{red}10}\hspace{20mm}\underbrace{\texttt{_ _ _ _ _ … _ _}}_{n-1} {\color{red}1}$$

We can’t have double 0’s in the $n-1$ or $n-2$ length strings, either. So, we now know that the number of strings length $n$ with no double 0’s is really just the number of strings of length $n-1$, plus the number of strings length $n-2$ that satisfy the condition. This fact is what defines the Fibonacci series.

We define $F_n=\text{number of strings length n with no double 0’s} = F_{n-1} + F_{n-2}$

We let $F_0=1$ by definition (kind of similar to the fact that $0!=1$) and $F_1=2$. There are 2 strings of length 1 that don’t have “00” (namely, “1” and “0”). $F_2 = F_1 + F_0 = 3$. This is also correct, since “10”, “01” and “11” are the only strings of length 2 that don’t have “00”. We could then go on to compute the rest of the series, but we won’t since you can find it on google in much less time than it would take for me to type a bunch of members of the set into this blog post.

 

II. Triple 0’s

Back to the original problem, we want to find out how many strings there are of length $n$ without “000”. Convince yourself that our solutions are of the following form

$$\underbrace{\texttt{_ _ _ _ _ … _ _}}_{n-3}{\color{red}100}\hspace{15mm}\underbrace{\texttt{_ _ _ _ _ … _ _}}_{n-2} {\color{red}10}\hspace{15mm}\underbrace{\texttt{_ _ _ _ _ … _ _}}_{n-1} {\color{red}1}$$

Our formula becomes $$B_n = B_{n-1} + B_{n-2} + B_{n-3}$$

$B_0=1, B_1 = 2, B_2 = 4$ are the starting points. There are 4 possible strings of length 2, and none of them have 3 zeros in a row (since there are only two characters). We can then compute the rest of the series, $B_3$ and $B_4$ are pretty easy to verify, but the higher orders would be difficult, so just trust me.

That’s all folks.

Author


Leave a Reply

Your email address will not be published. Required fields are marked *