10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is $1110$ OK? The maximal substring is three $1$s, but the maximal zero substring is one $0$. $\endgroup$ – Ross Millikan Apr 6 '17 at 23:52
  • 1
    $\begingroup$ $1110$ is okay according to the wording of the question. (it seems) But something like $111000$ is not okay. $\endgroup$ – sidhant Apr 7 '17 at 2:08
  • $\begingroup$ 1110 is OK, since the maximal substring is 111, and therefore not an odd length string of 0's. I think @IsaacBrowne misinterprets the 'or' in the definition that there need to be two such substrings. $\endgroup$ – Pieter21 Apr 17 '17 at 16:08
2
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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