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