Number of binary string with even length of 1s blocks.

Question

Consider a binary alphabet $D =\{0,1\}$. We want to determine number of binary string with length $n$, where every blocks of $1$s has even length. For example for $n = 4$ we have $0000$, $1100$, $0110$, $0011$, $1111$ - $5$ different variants.

My approach was to construct regular expression to determine this sequence. Let $\lambda = \emptyset$. Hence we have $(11\cup\lambda)(0^*(11)^*)^*$. Now we have generating function : $\frac{(x^2+1)(1-x)(1-x^2)}{(1-x)(1-x^2)-1}$, which doesn't correct (we may represent this function for series and find coefficient).

Maybe there is a simpler approach ? Or how can we find correct regexp?

Answer 1

Let $a_n$ be the number of admissible strings of length $n$.

We have $a_0=1$ (the empty string is admissible).

And $a_1 = 1$.

For each admissible string of length $n$, we can right-append a $0$ to get an admissible string of length $n+1$. And for each admissible string of length $n-1$ we can right-append $11$ to get an admissible string of length $n+1$. Every string of length $n+1$ can be generated by one of these two steps. Moreover every string of length $n+1$ is uniquely produced by these steps. Therefore $a_{n+1}=a_n+a_{n-1}$.

So the number of strings of length $n$ is $a_n=F_{n+1}$ where $F_k$ is the $k$th Fibonacci number ($F_0 = 0$, $F_1 = 1$, etc.)

Answer 2

Your approach using generating function is a good idea, but you have to start with an unambiguous regular expression. In your case, you could use $L = (0 + 11)^*$, which leads to the generating function $$ (t + t^2)^* = \frac{1}{1-t-t^2} $$ which is the generating function of the Fibonacci sequence as shown in this question.