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$ <-- prohibited because $dc$ appeared in the line above
$aeed$ <-- 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.