How many words of length $k$ on $l$ letters avoid a partial word? EDITED TO ADD: This question is now essentially answered; please see this blog entry for more details.  Thanks to everyone who posted comments and answers here.



ORIGINAL QUESTION

This is a hopefully smarter and better-informed version of a question I asked on MathOverflow.  When I asked that question, I did not even know the name of the area of mathematics my problem was in.  Now I am pretty sure it lies in Algorithmic Combinatorics on Partial Words.  (Recent book on the subject here.)

I want to make a list of words on $l$ letters.  Each word has length exactly $k$.  The deal is, if $a \lozenge ^j b$ is in the list, where $\lozenge$ is a wildcard/don't-care symbol, then $a \lozenge ^j b$ can never appear again in the list.  (The same holds true if $a=b$, or if $j=0$ and hence the prohibited subword is $ab$.)

Example where $k=4$ and $l=5$:

$abcd$
$bdce$
$dcba$ &lt;-- prohibited because $dc$ appeared in the line above
$aeed$ &lt;-- prohibited because $a \lozenge \lozenge d$ appeared on the first line

The literature on "avoidable partial words" that I have found has all been infinitary -- eventually some word pattern is unavoidable if the word size is large enough.  I would like to find finitary versions of such theorems.  So, question:


  Given a partial word of form $a \lozenge^j b$ in an alphabet of $l$ letters, how many words of length $k$ avoid it, and can they be explicitly produced in polynomial time?


I don't expect the above question to be difficult, and, unless there is a subtlety I am missing, I could calculate it myself.  The real reason I am posting on this site is because I need to know a lot more about the properties of such word lists for my application, so I am hoping someone can answer the followup question:


  Has this been studied in generality?  What are some papers that consider, not just whether a partial word is eventually unavoidable, but "how long it takes" before it becomes unavoidable?


Thanks.
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 (!).