[Math] Number of binary strings with ‘at least two consecutives’ constraints

co.combinatorics

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.

Best Answer

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*}

Related Question