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