Number of binary strings with 'at least two consecutives' constraints

Question

I'm trying to count the number of binary strings of length $n$ with the properties described below. Say we break the string into substrings (starting from left to right) of consecutive $0$'s or $1$'s. We must have:

1. The first substring can be of any length (from $1$ to $n$).

2. The last (ending at $n$) substring can be of any appropriate length (namely, a length between $1$ and whatever is left, is allowed).

3. All the intermediate substrings must have a length of at least $2$.

For example, if $n=10$, the following strings are viable:

$$0111001111$$

$$1110000001$$

$$1001100110$$

This, however, is not allowed: $010...$ or $110001101..$

I've tried to furnish a recursive relation but since there are different constraints on the first and last substrings, the recursion seems to go all the way back to the start.

I'm currently trying to think of this as a question of Stars and Bars and maybe get a (set of) Diophantine equation(s). No luck yet though.

Answer 1

We start considering words with no consecutive equal characters at all. These words are called Smirnov words or Carlitz words. (See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.)

A generating function for the number of Smirnov words over a binary alphabet is given by \begin{align*} \left(1-\frac{2z}{1+z}\right)^{-1}\tag{1} \end{align*}

To only get words with runs of length at least $2$ we replace in (1) each occurrence of $z$ by \begin{align*} z&\longrightarrow z^2+z^3+\cdots=\frac{z^2}{1-z}\\ \end{align*}

Doubling first and last character of a word implies we can focus on words containing solely of subword runs with length $\geq 2$ and the wanted number of occurrences of words of length $n$ is

\begin{align*} [z^{n+2}]&\left(1-\frac{2\frac{z^2}{1-z}}{1+\frac{z^2}{1-z}}\right)^{-1} =[z^{n+2}]\frac{1-z+z^2}{1-z-z^2}\tag{2} \end{align*}

with $\frac{1}{1-z-z^2}$ the generating function of the Fibonacci numbers $F_n$. We obtain from (2) the sequence \begin{align*} (F_{n+3}-F_{n+2}+F_{n+1})_{n\geq 1} &=\left(2F_{n+1}\right)_{n\geq 1}\\ &=(2,4,6,10,16,26,42,\ldots) \end{align*}

Answer 2

An answer has already been given, but let me additionally give you a meta-answer: the constraints you describe define a rational language on the alphabet $\{0,1\}$, namely a set of words (=finite strings) on this alphabet which can be described by a regular expression or finite automaton. In your case, a regular expression is easily described: $$ 00^*(111^*000^*)^*111^*00^* + 00^*(111^*000^*)^*11^* + 11^*(000^*111^*)^*00^* + 11^*(000^*111^*)^*000^*11^* + 0^* + 1^* $$ where "$^*$" means "any number (at least zero) of", and "$+$" (sometimes written "$|$") means "or" (the cases in the above sum are, moreover, disjoint: the first four describe the four cases where your string begins with $0$ and ends with $0$, begins with $0$ and ends with $1$, etc., and the last two make a special case of the sequences with just zeros or just ones — you might wish to add $\varepsilon$ to the expression if you consider the empty string to match your condition).

Now there are well known algorithms which will

• take a regular expression such as above and turn it into a finite automaton recognizing the language,

• turn this finite automaton into a deterministic one,

• compute the generating function of the language generated by a deterministic finite automaton.

Any book on rational languages or finite automata (e.g., the one by Sakarovitch¹) should discuss at least the first two and probably all three; the third is also discussed, e.g., here.

Alternatively, you can go through the "unambiguous regular expression" path, as discussed here: I don't know which is algorithmically more efficient in general, but in the case of your particular question, this works very well, as the above regular expression is unambiguous, and the procedure described here immediately produces the rational function $2\frac{x+x^2}{1-x-x^2}$.

My point is, this answers not only your particular question, but all questions about counting (or at least, producing a generating function for) the number of words described by any rational expression. Furthermore, these algorithms are actually implemented in the Vaucanson/Vaucanson2/Vaucanson-R/Wali/VCSN programs¹ (none of which are terribly usable at the present, unfortunately).

1. Full disclosure: Sakarovitch is my office neighbour.

Answer 3

Call strings in which all runs are of length at least 2 "duplicative strings".

Note that a duplicative string of length $n + 2$ either ends in a run of length exactly 2 or a run of length greater than 2. In the former case, it can be any duplicative string of length $n$, followed by the two characters opposite from this one's last character (assume here $n$ is positive). In the latter case, it can be any duplicative string of length $n + 1$ with its last character duplicated.

Thus, if we denote the number of duplicative strings of length $n + 2$ by $F(n + 2)$, we obtain the Fibonacci-type recurrence $F(n + 2) = F(n) + F(n + 1)$ for positive $n$.

This along with the obvious initial values $F(1) = 0$, $F(2) = 2$, and the observation made by others that the strings you are interested in are (by duplicating initial and final characters for those of length at least 1) in correspondence with duplicative strings of length $n + 2$, makes quick work of the problem. We have that $F(n)$ is twice the $(n - 1)$-th Fibonacci number (on the indexing whose $0$-th and $1$-st Fibonacci numbers are $0$ and $1$, respectively), and that the quantity you are interested in is $F(n + 2)$ (for positive $n$), which is therefore twice the $(n + 1)$-th Fibonacci number.