Counting Binary Strings (No block decompositions)

Question

The main question goes :

How many binary strings of length $n$ are there that do not contain an odd string of $0$'s as a maximal substring? (So $1001$ is okay but $10001$ is not)

A maximal substring is the substring of maximum length consisting of only $0$'s or only $1$'s.

I encountered this problem on the second page of a introductory book on combinatorics. I know how to solve this using block decompositions but it would be nice to have a combinatorial proof involving some form of counting argument or maybe a recursive formula. I believe there should be such a solution since the book does not assume any block decompositions before this question.

Answer 1

We denote with

• run of length $n$ a substring of $n$ consecutive, equal characters from a binary alphabet $\{0,1\}$.

• A maximum run of a string is a run with maximum length.

• An $n$-length zero-run is a run consisting of $n$ consecutive $0$s, and a one-run is specified accordingly.

We derive a generating function for the number $a_n$ of strings of length $n$ having no odd, maximum zero-run.

To avoid ambiguities we follow OPs comment and allow odd maximum runs of $1$'s together with odd runs of $0$'s as long as they are less in length than the odd maximum run of $1$'s which seems to be a somewhat more challenging problem.

The string $$0111\color{blue}{000}11$$ has an odd maximum zero-run of length $3$ equal to the maximum one-run and is not admissible. The string $$\color{blue}{0}111011$$ has an odd maximum zero-run of length $1$ less than the maximum one-run of length $3$ and is admissible.

We derive the number of admissible words of length $n$ by counting those words which are not admissible. The number of wanted words is $2^n$ minus this quantity. We do so by deriving a generating function \begin{align*} G^{(=2k+1,\geq 2k+1)}(z)\qquad\qquad\qquad k\geq 0 \end{align*} The first component of the index gives the maximum run length of $0$'s, the second component gives the maximum run length of $1$'s. So, $[z^n]G^{(=2k+1,\geq 2k+1)}(z)$ gives the number of words of length $n$ having maximum zero-runs of length $2k+1$ and maximum one-runs of length less or equal to $2k+1$.

It follows the number $a_n$ of admissible words of length $n$ is \begin{align*} a_n=2^n-[z^n]\sum_{k=0}^{\lfloor (n-1)/2\rfloor}G^{(=2k+1,\geq 2k+1)}(z)\qquad\qquad n\geq 0 \end{align*}

We build the generating functions $G(z)$ from the generating function of Smirnov words also called Carlitz words. These are words with no consecutive equal characters at all. (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} \end{align*}

Replacing occurrences of $0$ in a Smirnov word by one up to $2k+1$ zeros generates words having runs of $0$ with length less or equal $2k+1$. \begin{align*} z\longrightarrow z+z^2+\cdots+z^{2k+1}=\frac{z\left(1-z^{2k+1}\right)}{1-z} \end{align*}

The same can be done with ones and the resulting generating function is \begin{align*} G^{(\geq 2k+1,\geq 2k+1)}(z)=\left(1-2\cdot\frac{\frac{z\left(1-z^{2k+1}\right)}{1-z}}{1+\frac{z\left(1-z^{2k+1}\right)}{1-z}}\right)^{-1} &=\frac{1-z^{2k+1}}{1-2z+z^{2k+1}} \end{align*}

Since we need a generating function counting words having exactly $2k+1$ zero-runs we calculate \begin{align*} &G^{(=2k+1,\geq 2k+1)}(z)=G^{(\geq 2k+1,\geq 2k+1)}(z)-G^{(\geq 2k,\geq 2k+1)}(z)\\ &\qquad=\left(1-\frac{\frac{2z\left(1-z^{2k+1}\right)}{1-z}}{1+\frac{z\left(1-z^{2k+1}\right)}{1-z}}\right)^{-1} -\left(1-\frac{\frac{z\left(1-z^{2k}\right)}{1-z}}{1+\frac{z\left(1-z^{2k}\right)}{1-z}} -\frac{\frac{z\left(1-z^{2k+1}\right)}{1-z}}{1+\frac{z\left(1-z^{2k+1}\right)}{1-z}}\right)^{-1}\\ &\qquad=\frac{1-z^{2k+2}}{1-2z+z^{2k+2}}-\frac{(1-z^{2k+1})(1-z^{2k+2})}{1-2z+z^{2k+2}+z^{2k+3}-z^{4k+3}}\\ &\qquad=\frac{(1-z^{2})(1-z^{2k+2})z^{2k+1}}{(1-2z+z^{2k+2})(1-2z+z^{2k+2}+z^{2k+3}-z^{4k+3})} \end{align*}

We finally conclude

The number $a_n$ of admissible words of length $n$ is \begin{align*} a_n&=2^n-[z^n]\sum_{k=0}^{\lfloor (n-1)/2\rfloor}G^{(=2k+1,\geq 2k+1)}(z)\\ &=2^n-[z^n]\sum_{k=0}^{\lfloor (n-1)/2\rfloor} \frac{(1-z^{2})(1-z^{2k+2})z^{2k+1}}{(1-2z+z^{2k+2})(1-2z+z^{2k+2}+z^{2k+3}-z^{4k+3})}\tag{1} \end{align*} The sequence $(a_n)$ starts with \begin{align*} (a_n)_{n\geq 1}=(1,2,5,12,24,\color{blue}{48},95,187,367,724,\ldots) \end{align*}

Example: Let's calculate the number $a_6$ of admissible words of length $6$.

According to (1) we obtain the following series expansions (with some help of Wolfram Alpha) \begin{align*} G^{(=1,\leq 1)}(z)&=\frac{(1-z)^2(1-z^2)z}{(1-2z+z^2)(1-2z+z^2)}=\frac{(1+z)z}{1-z}\\ &=z+2z^2+2z^3+2z^4+2z^5+\color{blue}{2}z^6+2z^7+2z^8+2z^9+2z^{10}\cdots\\ G^{(=3,\leq 3)}(z)&=z^3+2z^4+5z^5+\color{blue}{12}z^6+25z^7+53z^8+109z^9+220z^{10}\cdots\\ G^{(=5,\leq 5)}(z)&=z^5+\color{blue}{2}z^6+5z^7+12z^8+28z^9+64z^{10}\cdots\\ \end{align*}

We conclude the number $a_6$ is given by \begin{align*} a_6&=2^6-[z^6]\sum_{k=0}^2G^{(=k,\leq k)}(z)\\ &=64-[z^6]\left(G^{(=1,\leq 1)}(z)+G^{(=3,\leq 3)}(z)+G^{(=5,\leq 5)}(z)\right)\\ &=64-\color{blue}{2}-\color{blue}{12}-\color{blue}{2}\\ &=48 \end{align*}

The $64-a_6=16$ non-admissible words are

\begin{array}{cccc} 1\color{blue}{0}1010&\color{blue}{0}10101\\ 001\color{blue}{000}&101\color{blue}{000}&011\color{blue}{000}&111\color{blue}{000}\\ \color{blue}{000}100&1\color{blue}{000}10&\color{blue}{000}110&01\color{blue}{000}1\\ 11\color{blue}{000}1&\color{blue}{000}101&1\color{blue}{000}11&\color{blue}{000}111\\ 1\color{blue}{00000}&\color{blue}{00000}1\\ \end{array}