3
$\begingroup$

I know my binary string is composed of exactly $n$ $1$s and $m$ $0$s. How many such strings are possible, if we add the constraint that they must not contain a specific given substring $S$ (whose length is $\leq n+m$)?

I am specifically interested in the answer in the case that $S=010$.

Note: I know how to determine the answer programatically / via dynamic programming. I'm looking for a more closed form / combinatoric solution.

For example, if $n=3$, $m=2$, and $S=010$, then the following would be all $7$ relevant ways: $$00111$$ $$01101$$ $$01110$$ $$10011$$ $$10110$$ $$11001$$ $$11100$$

$\endgroup$
  • 1
    $\begingroup$ Note: on first reading, I missed the condition that the number of $1's$ and $0's$ is specified. This question just deals with strings of a fixed length. Relevant, but not a duplicate. $\endgroup$ – lulu Oct 7 '16 at 23:43
  • 1
    $\begingroup$ The Goulden-Jackson Cluster Method : arxiv.org/pdf/math/9806036v1.pdf $\endgroup$ – arthur Oct 8 '16 at 0:41
3
$\begingroup$

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

We consider the set words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1\}$$ and the set $B=\{010\}$ of bad words, 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 of bad words with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[010]) \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[010])&=-s^3-s^2\text{weight}(\mathcal{C}[010])\tag{1}\\ \end{align*}

and get \begin{align*} \text{weight}(\mathcal{C})=-\frac{s^3}{1+s^2} \end{align*}

It follows

\begin{align*} f(s)&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-2s+\frac{s^3}{1+s^2}}\tag{2}\\ &=\frac{1+s^2}{1-2s+s^2-s^3}\\ &=1+2s+4s^2+7s^3+12s^4+\color{blue}{21}s^5\\ &\qquad+37s^6+65s^7+114s^8+200s^9+351s^{10}+\cdots \end{align*}

The last line was calculated with the help of Wolfram Alpha. The coefficient of $s^5$ shows there are $\color{blue}{21}$ valid words of length $5$ from the alphabet $\{0,1\}$ which do not contain the word $010$.

But we want to also keep track of the number of $0$'s and $1$'s. We get a refinement of $f(s)$ by marking the $0$ with $x$ and the $1$'s with $y$. We obtain from (1) \begin{align*} \text{weight}(\mathcal{C}[010])&=-x^2ys^3-xys^2\text{weight}(\mathcal{C}[010]) \end{align*} and get \begin{align*} \text{weight}(\mathcal{C})=-\frac{x^2ys^3}{1+xys^2} \end{align*}

Using this generalized weight we obtain from (2) a generating function $g(s;x,y)$ \begin{align*} g(s;x,y)&=\frac{1}{1-(x+y)s+\frac{x^2ys^3}{1+xys^2}}\\ &=\frac{1+xys^2}{1-(x+y)s+xys^2-xy^2s^3}\\ &=1+(x+y)s+(x^2+2xy+y^2)s^2+(x^3+2x^2y+3xy^2+y^3)\\ &\qquad+(x^4+2x^3y+4x^2y^2+4xy^3+y^4)s^4\\ &\qquad+(x^5+2x^4y+5x^3y^2+\color{red}{7}x^2y^3+5xy^4+y^5)s^5+\cdots \end{align*}

So, e.g. out of $2^5=32$ binary words of length $5$ there are $\color{blue}{21}$ valid words which do not contain $010$ and $\color{red}{7}$ of them contain $n=2$ zeros and $m=3$ ones:

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

$\endgroup$
  • $\begingroup$ How do you use WolframAlpha to compute the polynomial division for your final $g(s;x,y)$? I also have Wolfram Mathematica, but I cannot even get that to do the expansion.. $\endgroup$ – user1145925 Oct 10 '16 at 6:20
  • 1
    $\begingroup$ You could type: "series <expression in s,x,y> at s=0". This tells WA to expand at $s=0$ and arrange powers accordingly. For the expression above I used: "series 1/(1-(x+y)*s+x^2*ys^3/(1+xy*s^2)) at s=0 ". $\endgroup$ – Markus Scheuer Oct 10 '16 at 8:44
0
$\begingroup$

A recurrence and generating function.

For the case $S=010$, let $T_{n,m}$ be the number of ways.

$$T_{n,0}=1, T_{n,1}=n+1, T_{0,m}=1, T_{1,m}=2$$

The total with $n,m>1$, can be computed by recursion.

There are $T_{n-1,m}$ cases that end with $1$.

There are $T_{n,m-2}$ cases that end with $00$.

There are $T_{n-2,m-1}$ cases that end with $110$.

So $$T_{m,n} = T_{n-1,m}+T_{n,m-2} + T_{n-2,m-1}$$

From there, it is going to take some work to get a closed formula. You can probably use generating functions to get one. Letting:

$$f(x,y)=\sum_{m,n} T_{n,m}x^ny^m$$

The recurrence should give us something simple for:

$$f(x,y)(1-x-y^2-x^2y)=\sum_{m,n} a_{n,m}x^ny^m$$

The recurrense means that if $m,n>1$, then $a_{n,m}=0$.

My brain is having trouble getting the rest of this.

$\endgroup$
0
$\begingroup$

There are a total of $\frac{(m+n)!}{m!n!}$ strings of binary sequences with $m$ ones and $n$ zeros. There are $m+n-k*(S_m-S_n)+1$ spots where you could have $k$ strings $S$, where $S_n$ is the number of zeros in the string and $S_m$ is the number of ones in the string. The full formula is then $$\frac{(m+n)!}{m!n!}-\sum_{k=1}^G \frac{(m-kS_m+n-kS_n+k)!}{(m-kS_m)!(n-kS_n)!k!}$$ where $G=\left\lfloor\frac{m+n}{S_m+S_n}\right\rfloor$.

$\endgroup$
  • $\begingroup$ Your formula fails on the example case I provided in my question. Specifically, plugging in my provided example for your answer, we have $m=3$, $n=2$, and $S=010$. Thus, $S_n=2$, $S_m=1$, $G=1$, and your formula yields $9\neq 7$. $\endgroup$ – user1145925 Oct 8 '16 at 0:08
  • 1
    $\begingroup$ Sorry about that. I forgot to add a one in the numerator. $\endgroup$ – AlgorithmsX Oct 8 '16 at 0:11
  • $\begingroup$ @user1145925 My new formula produces the correct answer. $\endgroup$ – AlgorithmsX Oct 8 '16 at 0:40
  • $\begingroup$ Your new formula produces the correct answer for the specific case in the question. But modifying to $m=2$ and $n=3$, it gives the wrong answer. Enumerating, these are the $5$ possible strings: [00011, 00110, 01100, 10001, 11000], whereas your formula gives $4$. $\endgroup$ – user1145925 Oct 8 '16 at 0:53
  • 1
    $\begingroup$ I think the problem with my formula and that example is that it counts $[01010]$ twice as $[(010)10]$ and $[01(010)]$. $\endgroup$ – AlgorithmsX Oct 8 '16 at 1:09

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.