# How many binary strings (with a given number of occurrences of 0 and 1) are there that do not contain a given substring?

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

• 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. – lulu Oct 7 '16 at 23:43
• The Goulden-Jackson Cluster Method : arxiv.org/pdf/math/9806036v1.pdf – arthur Oct 8 '16 at 0:41

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}) \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C})&=-s^3-s^2\text{weight}(\mathcal{C})\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})&=-x^2ys^3-xys^2\text{weight}(\mathcal{C}) \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:

• 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.. – user1145925 Oct 10 '16 at 6:20
• 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 ". – Markus Scheuer Oct 10 '16 at 8:44

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.

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

• 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$. – user1145925 Oct 8 '16 at 0:08
• Sorry about that. I forgot to add a one in the numerator. – AlgorithmsX Oct 8 '16 at 0:11
• @user1145925 My new formula produces the correct answer. – AlgorithmsX Oct 8 '16 at 0:40
• 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$. – user1145925 Oct 8 '16 at 0:53
• I think the problem with my formula and that example is that it counts $$ twice as $[(010)10]$ and $[01(010)]$. – AlgorithmsX Oct 8 '16 at 1:09