I'm trying to figure out how many of the $\displaystyle x^L$ strings from an alphabet of $\displaystyle x$ characters, say $\displaystyle \left\{{a, b, c, d}\right\}$, do NOT contain a particular substring $\displaystyle s$ which itself contains no overlapping substrings. I figure that a decent recurrence relation is $\displaystyle S_L=4\times S_{L-1}-3\times S_{L-4}$ where $\displaystyle S_n$ is the number of $\displaystyle L$ length strings with no substring $\displaystyle s$ and:

$\displaystyle S_1=S_2=S_3=S_4 and S_5 = \frac{255}{256}.$

This is function-able but it would be great to have this as a closed form equation. Thanks in advance for any ideas.

Addie