How many words of length $k$ on $l$ letters avoid a partial word?
Here's a special case: the number of binary words of length $k$ such that no two ones appear consecutively is $F(k+3)$, where $F(n)$ is the $n^{th}$ Fibonacci number (starting with $F(1)=1, F(2)=1$). Proof is via the Zeckendorf representation.

EDIT: We can extend this initial special case into the slightly larger special case of $a\lozenge^0a$. Consider strings of length $k$ over an alphabet of size $l+1$ such that the letter $a$ does not appear twice consecutively. Let $f(k)$ be the number of such strings (which we will call "valid"). We claim that: $$f(k) = l*f(k-1) + l*f(k-2)$$ 
$$ f(0) = 1, f(1) = l+1$$
The intuition is that we can construct a valid string of length $k$ by either: a) adjoining any of the $l$ letters that are not $a$ to a valid string of length $k-1$, or b) adjoining the letter $a$ and then any other letter but $a$ to a valid string of length $k-2$.

You can verify that the following is a closed form for the above recurrence:
$$f(k) = \sum_{i=0}^{k} {{k+1-i}\choose{i}} l^{k-i}$$
where we understand ${{n}\choose{i}} = 0$ when $i&gt;n$.

EDIT #2: Let's knock out one more case -- a $\lozenge^0 b, a \neq b$. We'll call strings over an $l$-element alphabet that do not contain the substring $ab$, "valid" and let $S_k$ denote the set of valid strings of length $k$. Further, let's define $T_k$ to be the subset of $S_k$ consisting of strings starting with $b$ and $U_k$ to be those not starting with $b$. Finally, let $f(k) = |S_k|$, $g(k) = |T_k|$, $h(k) = |U_k|$. 

We observe that $g(0)=0, h(0)=1, f(0)=1$ and $g(1)=1, h(1)=l-1, f(1)=l$. Next, we infer the following recurrences:
\begin{eqnarray}
g(k+1) &amp;=&amp; f(k) \\
h(k+1) &amp;=&amp;(l-1)*h(k) + (l-2)*g(k)
\end{eqnarray}
The first comes from the fact that adding a $b$ to the start of any element of $S_k$ produces an element of $T_{k+1}$. The second comes from observing that we can construct an element of $U_{k+1}$ by adding any character but $b$ to the front of any element of $U_{k}$ or by adding any character but $a$ or $b$ to the front of any element in $T_k$.

Next, we rearrange the recurrence equations to obtain:
\begin{eqnarray}
f(k+1) &amp;=&amp; g(k+1) + h(k+1) \\
&amp;=&amp; f(k) + (l-1)*h(k) + (l-2)*g(k) \\
&amp;=&amp; f(k) + (l-1)*f(k) - g(k) \\
&amp;=&amp; l*f(k) - f(k-1)
\end{eqnarray}

We can get a rather opaque closed-form solution to this recurrence by mucking around a bit with generating function stuff or, if we're lazy, heading straight to Wolfram Alpha. However, with a little bit of googling and poking around in OEIS, we find that we actually have:
$$f(k) = U_k(l/2)$$
where $U_k$ is the $k^{th}$ Chebyshev polynomial of the second kind (!).