Number of bit strings of length $n$ with no $k_1+1$ consecutive 0s and no $k_2+1$ consecutive 1s.

Question

Just as the question asks. I am trying to calculate the number of bit strings of length $n$ with a maximum of $k_1$ consecutive $0s$ and $k_2$ consecutive 1s. Of course we assume $k_1+k_2\leq n$. I am trying to set up a recurrence but I am completely puzzled. I know that to not get two consecutive 0s, we have the recurrence $a_n=a_{n-1}+a_{n-2}$ with $a_1=2$ and $a_2=3$. However I can't seem to generalize this to no more than $k_1$ $0s$ especially that you have the second condition of no more than $k_2$ 1s.

Answer 1

This answer is based upon the Goulden-Jackson Cluster Method.

We consider the words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1\}$$ and the set $B=\{0^{k_1+1},1^{k_2+1}\}$ of bad words, $k_1,k_2\geq 0$, which are not allowed to be part of the words we are looking for.

We derive a generating function $f(s)$ with the coefficient of $s^n$ being the number of searched words of length $n$.

According to the paper (p.7) the generating function $f(s)$ is

\begin{align*} f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1} \end{align*} with $d=|\mathcal{V}|=2$, the size of the alphabet and $\mathcal{C}$ the weight-numerator with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[0^{k_1+1}])+\text{weight}(\mathcal{C}[1^{k_2+1}]) \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[0^{k_1+1}])&=-s^{k_1+1}-\text{weight}(\mathcal{C}[0^{k_1+1}])(s+s^2+\cdots+s^{k_1})\\ \text{weight}(\mathcal{C}[0^{k_2+1}])&=-s^{k_2+1}-\text{weight}(\mathcal{C}[0^{k_2+1}])(s+s^2+\cdots+s^{k_2})\\ \end{align*} and get \begin{align*} \text{weight}(\mathcal{C}[0^{k_1+1}])&=-\frac{s^{k_1+1}}{1+s+\cdots+s^{k_1}}=-\frac{s^{k_1+1}(1-s)}{1-s^{k_1+1}}\\ \text{weight}(\mathcal{C}[1^{k_2+1}])&=-\frac{s^{k_2+1}}{1+s+\cdots+s^{k_2}}=-\frac{s^{k_2+1}(1-s)}{1-s^{k_2+1}}\\ \end{align*}

It follows \begin{align*} \text{weight}(\mathcal{C})&=\text{weight}(\mathcal{C}[0^{k_1+1}])+\text{weight}(\mathcal{C}[1^{k_2+1}])\\ &=-(1-s)\left(\frac{s^{k_1+1}}{1-s^{k_1+1}}+\frac{s^{k_2+1}}{1-s^{k_2+1}}\right) \end{align*}

$$ $$

We obtain the generating function \begin{align*} f(s)&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &=\left(1-2s+\frac{s^{k_1+1}(1-s)}{1-s^{k_1+1}}+\frac{s^{k_2+1}(1-s)}{1-s^{k_2+1}}\right)^{-1}\tag{1}\\ \end{align*}

$$ $$

Example: $k_1=2,k_2=3$.

We consider the special case with the bad words $$B=\{0^{k_1+1},1^{k_2+1}\}=\{000,1111\}$$

We obtain from (1) with some help of Wolfram Alpha

\begin{align*} f(s)&=\left(1-2s+\frac{s^{3}(1-s)}{1-s^{3}}+\frac{s^{4}(1-s)}{1-s^{4}}\right)^{-1}\\ &=\frac{(1+s)(1+s^2)(1+s+s^2)}{1-s^2-2s^3-2s^4-s^5}\\ &=1+2s+4s^2+7s^3+12s^4+\color{blue}{21}s^5\\ &\qquad+36s^6+63s^7+109s^8+189s^9+328s^{10}+\cdots \end{align*}

We see the coefficient of $s^5$ is $21$. So, out of $2^5=32$ binary words of length $5$ there are $11$ invalid words containing subwords $\{000,1111\}$ which are marked blue in the table below.

\begin{array}{cccc} \color{blue}{00000}&\color{blue}{01000}&\color{blue}{10000}&\color{blue}{11000}\\ \color{blue}{00001}&01001&\color{blue}{10001}&11001\\ \color{blue}{00010}&01010&10010&11010\\ \color{blue}{00011}&01011&10011&11011\\ 00100&01100&10100&11100\\ 00101&01101&10101&11101\\ 00110&01110&10110&\color{blue}{11110}\\ 00111&\color{blue}{01111}&10111&\color{blue}{11111}\\ \end{array}

Answer 2

You can set up a set of coupled recurrences. Let $A(k,n)$ be the number of acceptable $n$ bit strings that end with $k\ 0$'s and $B(k,n)$ be the number of acceptable $n$ bit strings ending with $k\ 1$'s. Then $A(k+1,n+1)=A(k,n)$ and $A(1,n+1)=\sum_{i=0}^{k_2}B(i,n)$ and similarly for $B(k,n+1)$ Put the $A$'s and $B$'s into a column vector and you have a matrix that you multiply by the vector to increase the length of the string. You can diagonalize the matrix and find eigenvalues to find the asymptotic rate of growth.

Answer 3

Any string fulfilling the wanted constraints has one of the following structures: $$ 0^{a_1}1^{b_1}0^{a_2}1^{b_2}\ldots \qquad 1^{b_1}0^{a_1}1^{b_2}0^{a_2}\ldots $$ with $a_i\leq k_1, b_j\leq k_2$ and $\sum a_i+\sum b_j = n$. Assume that we want to compute how many strings are there of the $0^{a_1}1^{b_1}0^{a_2}1^{b_2}0^{a_3}$ kind. They are given by the coefficient of $x^n$ in the product $$ \left(1+x+x^2+\ldots+x^{k_1}\right)^3\cdot\left(1+x+x^2+\ldots+x^{k_2}\right)^2 = p_{k_1}(x)^3 p_{k_2}(x)^2$$ hence by accounting for all possible kinds, the answer is given by the coefficient of $x^n$ in $$ \sum_{r\geq 0}\left(p_{k_1}(x)^r p_{k_2}(x)^{r+1}+p_{k_1}(x)^{r+1}p_{k_2}(x)^r\right) =\color{red}{\frac{p_{k_1}(x)+p_{k_2}(x)}{1-p_{k_1}(x)\,p_{k_2}(x)}}.$$

Answer 4

Let me to begin with changing the $k$s to $k_0$ and $k_1$, so to help and remember their association with the values.

First step is to fix the total number of ones at , let say $0 \leqslant q \leqslant n$ (and the number of zeros is consequently fixed). We know the total number of ways to obtain strings of length $n$ with $q$ ones, so we will at end accomodate for that. Then your scheme is equivalent to many other combinatorial ones, e.g. number of lattice paths from $(0,0)$ to $(n-q,q)$ with steps from $\left\{ {\left( {1 \ldots k_0 ,0} \right),\left( {0,1 \ldots k_1 } \right)} \right\}$.
After fixing the total number of $1$s, let now fix the number of $1$-blocks at $m$. The number of $0$-blocks will be either $m$ (if the string starts and ends with different values), or $m-1$ (starts and ends with $1$) or $m+1$ (starts and ends with $0$).
The number of ways to arrange $q$ ones into $m$ blocks with no more than $k_1$ in each, is the number of compositions of $q$ in $m$ parts of max size $k_1$. An expression for that can be derived from the answers to Rolling dice problem (re. to there for details), where we have: $$ N_{\,b} (s,r,m) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s \hfill \\ \end{gathered} \right. $$ which can be expressed as $$ N_{\,b} (s,r,m)\quad \left| {\;0 \le {\rm integers}\;s,r,m} \right.\quad = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,{s \over r}\, \le \,m} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{ m \cr k \cr} \right)\left( \matrix{ s + m - 1 - k\left( {r + 1} \right) \cr s - k\left( {r + 1} \right) \cr} \right)} $$ In our case, since the number of $1$s goes from $1$ to $k_1$, we shall replace $r$ with $k_1-1$ and $s$ with $q-m$.
Now we shall intersperse the $1$-blocks into the $0$-blocks "comb-to-comb". The number of ways to make up the $0$-blocks follows the same formula, with the appropriate parameters.
Considering that the "starting-block($0$/$1$)-end-block($0$/$1$)" represents a partition of the considered strings, it is not difficult to make up the four parts and conclude: $$ \begin{gathered} N(k_{\,0} ,k_{\,1} ,n,q,m) = \hfill \\ = N_b (q - m,k_{\,1} - 1,m)\left( {N_b (n - q - m + 1,k_{\,0} - 1,m - 1) + 2N_b (n - q - m,k_{\,0} - 1,m) + N_b (n - q - m - 1,k_{\,0} - 1,m + 1)} \right) \hfill \\ \end{gathered} $$ In summing through $m$ and then $p$ (after multiplying by C(n,q)), note that in the $N_{\,b} (s,r,m)$ formula, the bounds in the summation and in the parameters may be omitted (practically: stretched from $0$ to a suitable max), because the binomials (as defined and as written), or the sum itself, are null for $m<k$ and $mr<s$, etc., being enough to ensure that $0 \leqslant r$.

Answer 5

Here is a comment showing how to compute the generating functions from first principles. We may then continue as in the answer by @MarkusScheuer.

Using $z$ for zero and $w$ for one we have the generating function

$$(1+z+z^2+\cdots+z^{k_1}) \sum_{q\ge 0} (w+w^2+\cdots+w^{k_2})^q (z+z^2+\cdots+z^{k_1})^q \\ \times (1+w+w^2+\cdots+w^{k_2}).$$

As we are only interested in the count we may write this as

$$(1+z+z^2+\cdots+z^{k_1}) \sum_{q\ge 0} (z+z^2+\cdots+z^{k_2})^q (z+z^2+\cdots+z^{k_1})^q \\ \times (1+z+z^2+\cdots+z^{k_2}).$$

This is

$$\frac{1-z^{k_1+1}}{1-z} \left(\sum_{q\ge 0} z^q \frac{(1-z^{k_2})^q}{(1-z)^q} z^q \frac{(1-z^{k_1})^q}{(1-z)^q}\right) \frac{1-z^{k_2+1}}{1-z} \\ = \frac{1-z^{k_1+1}}{1-z} \frac{1-z^{k_2+1}}{1-z} \frac{1}{1-z^2(1-z^{k_1})(1-z^{k_2})/(1-z)/(1-z)} \\ = \frac{(1-z^{k_1+1})(1-z^{k_2+1})} {1-2z+z^2-z^2(1-z^{k_1})(1-z^{k_2})} \\ = \frac{1-z^{k_1+1}-z^{k_2+1}+z^{k_1+k_2+2}} {1-2z+z^{k_1+2}+z^{k_2+2}-z^{2+k_1+k_2}}.$$

Some Maple code to verify these follows.

RL :=
proc(n, k1, k2)
    option remember;
    local ind, d, pos, cur, run, runs, res,
    zmax, wmax;

    res := 0;

    for ind from 2^n to 2*2^n-1 do
        d := convert(ind, base, 2);

        cur := -1; pos := 1;
        run := []; runs := [];


        while pos <= n do
            if d[pos] <> cur then
                if nops(run) > 0 then
                    runs :=
                    [op(runs), [run[1], nops(run)]];
                fi;

                cur := d[pos];
                run := [cur];
            else
                run := [op(run), cur];
            fi;

            pos := pos + 1;
        od;

        runs := [op(runs), [run[1], nops(run)]];

        zmax := max(seq(`if`(r[1] = 0, r[2], 0), r in runs));
        wmax := max(seq(`if`(r[1] = 1, r[2], 0), r in runs));

        if zmax <= k1 and wmax <= k2 then
            res := res + 1;
        fi;
    od;

    res;
end;

X :=
proc(n, k1, k2)
option remember;
local gf;

    gf :=
    (1-z^(k1+1)-z^(k2+1)+z^(k1+k2+2))
    /(1-2*z+z^(k1+2)+z^(k2+2)-z^(k1+k2+2));

    coeftayl(gf, z=0, n);
end;