How many binary strings of length 10 are there that don't contain either of the substrings 101 or 010?
I've tried doing some casework, thinking that there wouldn't be too many cases, but it didn't work. I split my cases up into 1) string begins with 1 and 2) string begins with 0.
Casework might not be the best option here. I think an ideal method to solve this would involve some sort of recursion, but I'm not sure where I should start.
Best Answer
This answer is based upon the Goulden-Jackson Cluster Method, a generating function method encoding PIE, the principle of inclusion-exclusion. We consider the set of words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1\}$$ and the set $B=\{010,101\}$ 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 wanted words of length $n$.
According to the paper (p.7) the generating function $f(s)$ is \begin{align*} \color{blue}{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}$ being the weight-numerator of bad words with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[010])+\text{weight}(\mathcal{C}[101])\tag{2} \end{align*}
The additional terms on the right-hand side of (3) take account of the overlapping of $01\color{blue}{0}$ with $\color{blue}{0}10$ and of $0\color{blue}{10}$ with $\color{blue}{10}1$ and similarly in (4). Solving the linear equations in the unknowns $\text{weight}(\mathcal{C}[010])$ and $\text{weight}(\mathcal{C}[101])$ in (3) and (4) gives \begin{align*} \text{weight}(\mathcal{C}[010])=\text{weight}(\mathcal{C}[101])=-s^3\frac{1+s-s^2}{1+2s+s^2-s^4} \end{align*} from which according to (1) and (2) \begin{align*} \color{blue}{f(s)}&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-2s+2s^3\frac{1+s-s^2}{1+2s+s^2-s^4}}\\ &\,\,\color{blue}{=\frac{1+s+s^2}{1-s-s^2}} \end{align*} follows. Series expansion of $f$ at $s=0$ gives \begin{align*} f(s)&=\frac{1+s+s^2}{1-s-s^2}\\ &=1 + 2 s + 4 s^2 + 6 s^3 + 10 s^4 + 16s^5+26s^6\\ &\qquad + 42 s^7+68s^8+110s^9 + \color{blue}{178} s^{10} + 288s^{11} +\cdots \end{align*} where the last line was calculated with the help of Wolfram Alpha.
Result: The blue marked coefficient of $s^{10}$ shows there are $\color{blue}{178}$ words of length $10$ over the alphabet $\mathcal{V}$ which do not contain $010$ or $101$.