3
$\begingroup$

This question is giving me a lot of trouble. It's taking a very long time to solve.

My Work

I'll find how many strings have consecutive zeros and then deduct that from the total amount of strings

Case I: The Length of String is $1$

$0$ of these strings have consecutive $0$

Case II: The Length of String is $2$

$1$ string $00$ has consecutive $0$s

Case III: The Length of String is $3$

The string must contain at least $2$ zeros to have consecutive zeros. There are $2$ strings comprised of $1,0,0$ with consecutive zeros. There is one string comprised of $0,0,0$ that will have consecutive zeros. 3 strings.

Case IV: The Length of String is $4$

When there are two zeros and two 1s there are 3 consecutive strings. When there are 3 zeros and one 1s there must be 4 arrangements with consecutive zeros. When there are 4 zeros there are obviously 1 arrangement with 0. $3+4+1 = 8$ strings with consecutive zeros

Case V: The Length of String is $5$

2 0s and 3 1s. There are 4 strings with consecutive zeros. 3 0s and 2 1s there are 9 strings with consecutive zeros. 4 0s there are 5 strings with consecutive zeros. 5 zeros there is one string with consecutive zeros. $4+9+5+1 = 19$ strings with consecutive zeros.

Case VI: The Length of String is $6$

2 zeros there are 5 strings with consecutive zeros. 3 zeros there are 20 strings with consecutive zeros. 4 zeros and two 1s 15 total strings with consecutive zeros. 5 zeros means there are 6 strings with consecutive zeros. Six zeros means there is 1 string with consecutive zeros. $5+20+15+6+1 = 47$ strings with consecutive 0s.

$2^1+2^2+2^3+2^4+2^5+2^6 = 126$

$0+1+3+8+19+47 = 78$

Total Number of Strings Without Consecutive Zeros = 126-78 = 48

My Question:

Is my answer correct and is there a better way to do this question?

$\endgroup$
  • 2
    $\begingroup$ Length $6$ is much too large, there are only $64$ strings. I would count the empty string, but that's a matter of taste. The numbers with no consecutive $0$'s are Fibonacci numbers. $\endgroup$ – André Nicolas Jan 10 '15 at 2:35
  • $\begingroup$ @AndréNicolas thanks for the catch. I've edited my answer accordingly. What do you mean they're the Fibonacci Numbers? $\endgroup$ – Dunka Jan 10 '15 at 2:40
  • $\begingroup$ The answer by Brian M. Scott explains everything. By the way, it is $43$ not $47$ ($64-21$). $\endgroup$ – André Nicolas Jan 10 '15 at 2:42
  • $\begingroup$ This question is good, will help me prepare for an upcoming quiz today in MACM 201. $\endgroup$ – Belphegor Jan 14 '15 at 19:57
10
$\begingroup$

Look at the numbers of strings of each length without consecutive zeroes:

$$\begin{array}{rcc} \text{Length:}&0&1&2&3&4&5&6\\ \text{Nr. of strings:}&1&2&3&5&8&13&21 \end{array}\tag{1}$$

That bottom row should look familiar: it’s the Fibonacci numbers. Even if you don’t spot that, you should notice that each number is the sum of the previous two. A little thought reveals the reason. Consider the strings of length $n$ without consecutive zeroes. The ones that end in $1$ can all be obtained by adding a $1$ on the end of an allowable string of length $n-1$, and the ones that end in $0$ can all be obtained by adding $10$ to the end of an allowable string of length $n-2$. Thus, if $a_n$ is the number of strings of length $n$ without consecutive zeroes, we have $a_n=a_{n-1}+a_{n-2}$, the same rule that gives the Fibonacci numbers; only the starting point is different. (In fact, $a_n=F_{n+2}$.)

If you see all of this, you can easily write down the bottom row of $(1)$ and add up the entries to get $53$. However, unless you’ve already had a fair bit of experience, it may very well be just as fast to use your approach (though your number for $n=6$ is off).

$\endgroup$
  • $\begingroup$ By using $\sum_0^m F_k=F_{m+2}-1$ we can show that our number is $F_{10}-2$. $\endgroup$ – André Nicolas Jan 10 '15 at 3:21
  • $\begingroup$ @André: I was debating whether to mention that. Now I don’t have to debate any more! $\endgroup$ – Brian M. Scott Jan 10 '15 at 3:22
  • $\begingroup$ Probably you were right, overkill. $\endgroup$ – André Nicolas Jan 10 '15 at 3:31
2
$\begingroup$

A book by Sedgewick and Flajolet, An Introduction to the Analysis of Algorithms, shows a way to count the number of binary strings without consecutive zeros.

Let $\mathcal G$ be a class of binary strings with no two consecutive 0 bits. This kind of a string can either be empty (represented as $\epsilon$), a single 0 bit ($\mathcal{Z}_0$) or a single 1 bit ($\mathcal{Z}_1$) or 01 followed by a string with no two consecutive 0 bits.

This can be symbolically written as $$ \mathcal{G} = \epsilon + \mathcal{Z}_0 + (\mathcal{Z}_1 + \mathcal{Z}_0 \times \mathcal{Z}_1) \mathcal{G}$$ and by using the generating functions that enumerate these classes (1 for $\epsilon$ and z for $\mathcal Z$) and the rules for their combination ($A(z) + B(z)$ enumerates $\mathcal A + \mathcal B$ and $A(z)B(z)$ enumerates $\mathcal A \times \mathcal B$) one gets an equation for the generating function $G(z)$ enumerating strings in the class $\mathcal G$ $$ G(z) = 1 + z + (z + z^2) G(z) .$$ Solving for $G(z)$ gives $$ G(z) = \frac{1 + z}{1 - z - z^2} $$ and by observing that the generating function for the Fibonacci sequence can be written as $$F(z) = \frac{z}{1-z-z^2} $$ one can see that the answer (number of binary strings of length $N$ without consecutive zeros) can be written in terms of the Fibonacci numbers $$ G_N = F_N + F_{N+1} = F_{N+2} .$$

The answer to the original question is then $$ \sum_{i=0}^6 G_i = \sum_{i=0}^6 F_{i+2} = F_2 + F_3 + F_4 + F_5 + F_6 + F_7 + F_8 $$ $$ = F_4 + F_6 + 2F_8 = 3 + 8 + 2*21 = 53. $$

$\endgroup$

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.