1
$\begingroup$

This question already has an answer here:

I need to calculate no of possible substrings containing "00" as a substring. I know the length of the binary string.

Eg: for a string of length 4, possible substrings are: 0000 0001 0010 0011 0100 1000 1001 1100

I just need the number of possible combinations, not enumerate all of them.

$\endgroup$

marked as duplicate by MJD, Andrey Rekalo, Start wearing purple, Thomas, Amzoti Aug 13 '13 at 17:41

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

Let $a_n$ be the number of strings of length $n$ that do contain $00$, and let $b_n$ be the number that don't; of course $b_n=2^n-a_n$, but it's actually easier to determine $b_n$. Consider a string of length $n$ that does not contain $00$. If it ends in $1$, it can be obtained from a string of length $n-1$ that does not contain $00$ by appending a $1$. If it ends in $0$, it can be obtained from a string of length $n-2$ that does not contain $00$ by appending $10$. Assuming that $n\ge 2$, every string of length $n$ that does not contain $00$ is obtained in exactly one of these two ways, so $b_n=b_{n-1}+b_{n-2}$. Clearly $b_0=1$, since the empty string does not contain $00$, and $b_1=2$. The recurrence is the same as that for the Fibonacci numbers, $b_0=F_2$, and $b_1=F_3$, so in general we have $b_n=F_{n+2}$ and therefore

$$a_n=2^n-F_{n+2}\;.$$

Using the closed-form expressions in the linked article, we can write

$$a_n=2^n-F_{n+2}=2^n-\frac1{\sqrt5}\left(\varphi^{n+2}-\widehat\varphi^{n+2}\right)=2^n-\left\lfloor\frac{\varphi^{n+2}}{\sqrt5}+\frac12\right\rfloor\;,$$

where $\varphi=\frac12\left(1+\sqrt5\right)$ and $\widehat\varphi=\frac12\left(1-\sqrt5\right)$.

$\endgroup$
  • $\begingroup$ @Czechnology: You’re welcome! $\endgroup$ – Brian M. Scott Nov 5 '14 at 17:39

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