3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ This is truly beautiful! Thank you for sharing this answer!! Really amazing! $\endgroup$ – AspiringMat Oct 4 '16 at 16:16
  • $\begingroup$ @AspiringMat: Many thanks for your nice comment! Good to see the answer us useful! :-)Btw. If you search for patterns of this kind in a word with given chars there is another cool technique. $\endgroup$ – Markus Scheuer Oct 4 '16 at 20:08
2
$\begingroup$

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)}}.$$

$\endgroup$
2
$\begingroup$

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;
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the answer. How would I cope if there was even further constrictions on the number of 1s and 0s we can use. For example $n_1$ 0s with max $k_1$ consecutive 0s and $n_2$ 1s with max $k_2$ consecutive 1s. Can we employ the same method? Just out of curiosity. $\endgroup$ – AspiringMat Sep 29 '16 at 14:26
  • $\begingroup$ As asked, you have now required a fixed length of the string at $n_1+n_2$. This is more easily handled by picking the places for the $1$'s and making sure you satisfy the restrictions, using inclusion/exclusion. If you want to require a certain string of $1$'s but forbid some longer string, yes, but the number of states can get unwieldy. Each $A(-,k)$ and $B(-,k)$ represents a state in a Markov chain. You need a new variable for each state, so will need $C(-,k)$ to be unacceptable strings ending in $k\ 1$'s $\endgroup$ – Ross Millikan Sep 29 '16 at 14:32
  • $\begingroup$ @RossMillikan: Anyway, the ordinary generating function associated to this problem is easy to write down, so instead of considering a huge Markov chain and diagonalize it, it is faster to look at the zeroes of $1-p_{k_1}(x)p_{k_2}(x)$ - i.e. we already know the characteristic polynomial, despite "hugeness". $\endgroup$ – Jack D'Aurizio Sep 29 '16 at 15:48
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

We consider the binary alphabet $V=\{0,1\}$ and look for the number $g_n(k_1,k_2)$ of binary words of length $n$ which contain runs of $0$ with length at most $k_1$ and runs of $1$ with length at most $k_2$.

Words with no consecutive equal characters at all are called Smirnov 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*}

We replace occurrences of $0$ in a Smirnov word by one up to $k_1$ zeros to generate strings having runs of $0$ with length at most $k_1$ \begin{align*}\ z\longrightarrow z+z^2+\cdots+z^{k_1}=\frac{z\left(1-z^{k_1}\right)}{1-z}\tag{2} \end{align*}

We replace occurrences of $1$ in a Smirnov word by one up to $k_2$ ones to generate strings having runs of $1$ with length at most $k_2$ \begin{align*} z\longrightarrow z+z^2+\cdots+z^{k_2}=\frac{z\left(1-z^{k_2}\right)}{1-z}\tag{3} \end{align*}

We substitute (2) and (3) in (1) and obtain

\begin{align*} &\left(1- \frac{\frac{z\left(1-z^{k_1}\right)}{1-z}}{1+\frac{z\left(1-z^{k_1}\right)}{1-z}} - \frac{\frac{z\left(1-z^{k_2}\right)}{1-z}}{1+\frac{z\left(1-z^{k_2}\right)}{1-z}}\right)^{-1}\\ &\qquad=\frac{(1+z)\left(1-z^{k_1}\right)\left(1-z^{k_2}\right)}{1-z+2z^2-\left(z^{k_1+1}+z^{k_2+1}\right)(1+z)-z^{k_1+k_2+2}(1+3z)}\tag{4} \end{align*}

Denoting with $[z^n]$ the coefficient of $z^n$ in a series we obtain from (4) the number of wanted words as \begin{align*} \color{blue}{g_n(k_1,k_2) =[z^n]\frac{(1+z)\left(1-z^{k_1}\right)\left(1-z^{k_2}\right)}{1-z+2z^2-\left(z^{k_1+1}+z^{k_2+1}\right)(1+z)-z^{k_1+k_2+2}(1+3z)}}\tag{5} \end{align*}

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

We consider the special case with words of length $5$ containing runs of $0$ with length at most $2$ and runs of $1$ with length at most $3$

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

\begin{align*} \sum_{n=0}^\infty g_n(k_1,k_2)z^n&=\frac{(1+z)(1-z^3)(1-z^4)}{1-z+2z^2-(z^3+z^4)(1+z)-z^7(1+3z)}\\ &=\frac{(1+z)(1+z^2)(1+z+z^2)}{1-z^2-2z^3-2z^4-z^5}\\ &=1+2z+4z^2+7z^3+12z^4+\color{blue}{21}z^5+36z^6+63z^7+\cdots \end{align*}

We see the coefficient of $z^5$ is $21$. The $21$ valid words are $$ \begin{array}{cccc} 00100&01001&10010&11001\\ 00101&01010&10011&11010\\ 00110&01011&10100&11011\\ 00111&01100&10101&11100\\ &01101&10110&11101\\ &01110&10111& \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.