I have been trying to find a way to count the number of binary strings of length $n$ such that it has no three consecutive $1$'s, but also either has exactly $k$ $1$'s or exactly $k$ $0$'s.
For example, if $n = 4$ and $k = 3$, then there are six valid such binary strings: $0001$, $0010$, $0100$, $1000$, $1011$, and $1101$.
Similar to this post, we can model the problem with a recurrence relation.
My first attempt is to define the recurrence relation $F(n,p,q)$ denoting the number of binary strings of length $n$ with no three consecutive $1$'s with exactly $p$ $1$'s and $q$ $0$'s.
Here, I have $F(n,p,q) = F(n-3,p-2,q-1) + F(n-2,p-1,q-1) + F(n-1,p,q-1)$ for $n \geq 4, p \geq 2, q \geq 1$, with the following initial conditions:
$$
F(n,p,q) =
\begin{cases}
0 & \text{if } n = 0, \text{ or } p + q \neq n\\
1 & \text{if } p = 0, q = n\\
n & \text{if } p = 1, q = n – 1 \text{ or } n = p = 2, q = 0\\
3 & \text{if } (n,p,q) = (3,1,2) \text{ or } (n,p,q)=(3,2,1)
\end{cases}
$$
Essentially, the recurrence relation is derived from how such binary strings of length $n$ can be formed by strings of the form $s011$, $s01$, or $s0$, where $s$ is again a binary string with no three consecutive ones of length $n-3$, $n-2$, or $n-1$, respectively.
The string $s011$ adds two extras $1$'s and one extra $0$ to $s$.
The string $s01$ adds one extra $0$ and one extra $1$ to $s$.
Lastly, the string $s0$ adds an extra $0$ to $s$.
Notice that to get the answer to our original problem, we can define a function $\tilde{F}(n,k)$ representing the number of binary strings of length $n$ with no three consecutive ones consisting of either $k$ ones or $k$ zeros as
$$
\tilde{F}(n,k) =
\begin{cases}
F(n,n/2,n/2), \text{ if $n$ is even and $k = n/2$} \\
F(n,k,n-k) + F(n,n-k+k), \text{ otherwise}
\end{cases}
$$
Using the idea from this post, we can use generating functions to count the exact formula for the recurrence relation $F(n,p,q)$.
After doing some calculations (you can see the detail here if interested), this is the generating function I found we can use for $F(n,p,q)$:
$$
G(x,y,z) = \sum_{n \geq 0, p \geq 0, q \geq 0} F(n,p,q) x^n y^p z^q = \frac{2x^3y^2z – x^2y^2 – x^2yz – xy – xz}{x^3y^2z + x^2yz + xz – 1}
$$
Now, the question is how do we compute the coefficient $[x^ny^pz^q] \left( \frac{2x^3y^2z – x^2y^2 – x^2yz – xy – xz}{x^3y^2z + x^2yz + xz – 1} \right)$?
I am really new to generating functions and have been struggling because of how the denominator cannot be factorized, hence we cannot do any useful partial fractions on it. Also, I have not been very successful in finding a common series similar to the one we are investigating.
Any ideas or sources that might be helpful to solve this?
Is it even possible?
If it is impossible, can we at least get the asymptotic upper bound for such a recurrence relation?
I conjectured that the upper bound for $F(n,p,q)$ is exponential in terms of $n$, $p$, and $q$, but I do not know how to prove it.
Thanks in advance.
Update: As suggested by @VTand, we can redefine $F$ in terms of only $p$ and $q$ as $n$ is a redundant variable. Then, we have $F(p,q) = F(p-2,q-1) + F(p-1,q-1) + F(p,q-1)$ for $p \geq 2, q \geq 1$ with these initial conditions:
$$
F(p,q) = \begin{cases}
0 & \text{if $q = 0, p > 2$}\\
1 & \text{if $p = 0$ or $(p,q) = (2,0)$}\\
q + 1 & \text{if $p = 1$}
\end{cases}
$$
Apparently, the generating function we can work with now is much simpler (you can see the calculation here if interested), that is:
$$
G(x,y) = \sum_{p \geq 0,q \geq 0} F(p,q) x^p y^q = \frac{x^2 + x + 1}{1 – y(x^2 + x + 1)}
$$
To calculate for $F(p,q)$, we can use the value $[x^py^q] \left( \dfrac{x^2 + x + 1}{1 – y(x^2 + x + 1)} \right)$, i.e. the coefficient of $x^py^q$ of the power series $G(x,y)$. However, I am still struggling to extract the coefficient or determine the asymptotic upper bound. Any help would be very much appreciated.
Best Answer
It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write for example \begin{align*} [x^k](1+x)^n=\binom{n}{k}\tag{1} \end{align*}
Comment:
In (3.1) we use the geometric series expansion.
In (3.2) we select the coefficient of $y^{n-k}$.
In (3.3) we apply the binomial theorem.
In (3.4) we use the linearity of the coefficient of operator and apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.
In (3.5) we select the coefficient of $x^{k-2j}$.
Plausibility check $n=4, k=3$:
We use OPs example and calculate the number of valid strings of length $n=4$ with $k=3$ $1$s without runs of length $3$. \begin{align*} \color{blue}{0001\quad0010\quad0100\quad1000\quad1011\quad1101}\tag{5.1} \end{align*} We obtain from (4) \begin{align*} \color{blue}{([x^3y]+[xy^3])G(x,y)}&=\sum_{j=0}^1\binom{2}{j}\binom{2-j}{3-2j}+\sum_{j=0}^0\binom{4}{j}\binom{4-j}{1-2j}\\ &=\left(\binom{2}{0}\binom{2}{3}+\binom{2}{1}\binom{1}{1}\right)+\binom{4}{0}\binom{4}{1}\\ &=0+2+4\tag{5.2}\\ &\,\,\color{blue}{=6} \end{align*} in accordance with (5.1).
Add-on - Calculation of $G(x,y)$:
Here is an alternate method to calculate the generating function $G(x,y)$ based upon the so-called Goulden-Jackson Cluster Method.
According to the paper (p.7) the generating function $f(s)$ is \begin{align*} f(s)=\frac{1}{1-ds-\text{w}(\mathcal{C})}\tag{6.1} \end{align*} with $d=|\mathcal{V}|=2$, the size of the alphabet and $\mathcal{C}$ the weight-numerator of bad words with \begin{align*} \text{w}(\mathcal{C})=\text{w}(\mathcal{C}[111]) \end{align*}
We calculate according to the paper \begin{align*} \text{w}(\mathcal{C}[111])&=-(sx)^3-sx\cdot \text{w}(\mathcal{C}[111])-(sx)^2\cdot\text{w}(\mathcal{C}[111])\\ \end{align*} where we additionally mark occurrences of $1$s with $x$ and occurrences of $0$s with $y$. We obtain \begin{align*} \text{w}(\mathcal{C})=\text{w}(\mathcal{C}[111])=-\frac{(sx)^3(1-(sx))}{1-(sx)^3}\tag{6.2} \end{align*}