How many words of length $k$ on $l$ letters avoid a partial word?

Question

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.

Answer 1

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>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) &=& f(k) \\ h(k+1) &=&(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) &=& g(k+1) + h(k+1) \\ &=& f(k) + (l-1)*h(k) + (l-2)*g(k) \\ &=& f(k) + (l-1)*f(k) - g(k) \\ &=& 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 (!).

Answer 2

A completely different approach for the first question reuses the answers to the recent question on generating words in a regular language: it suffices to apply these algorithms for length $k$ on the regular language $\Sigma^\ast a\Sigma^j b\Sigma^\ast$ where $\Sigma$ is the alphabet.

Answer 3

Updated: this answer is incorrect:

assuming $j$ is fixed, we can count the number of ways a pattern $a\lozenge^j b$ can be matched: the first $a$ symbol can be matched at some position $1\leq i\leq k-j-1$, and we have $l^{i-1}$ possibilities before that point, $l^j$ between $a$ and $b$, and $l^{k-j-i-1}$ for the remainder of the string, thus a total of $$\sum_{i=1}^{k-j-1}l^{i-1}\cdot l^{j}\cdot l^{k-j-i-1}=(k-j-1)l^{k-2}$$ cases. As noted by Tsuyoshi Ito in the comments, this count is not the number of different words matching $a\lozenge^j b$ since a single word could match the same pattern in different ways. For instance $aa$ is matched three times in $aaaa$, $ab$ two times in $abab$, and $a\lozenge b$ two times in $aabb$. We can try to count the number of ways of matching patterns several times and exhibit an "inclusion-exclusion" expression, but the ways pattern might overlap makes this too long.

---

For the first question, under the understanding that $j$ is not fixed, i.e. that we want to avoid embedding the word $ab$:

• either $a$ the first symbol never appears, which accounts for $(l-1)^k$ possible words,
• or $a$ appears first in some position $1\leq i\leq k$, then we cannot use $b$ in the remainder of the word: there are $(l-1)^{i-1}$ choices for the factor up to $a$, and $(l-1)^{k-i}$ choices for the remainder, giving in total $\sum_{i=1}^k(l-1)^{i-1}\cdot(l-1)^{k-i}=k(l-1)^{k-1}$ possible words. Whether $a=b$ is irrelevant.

For the second question, I don't have much to suggest; there is a relation with word embeddings, but the results I know about bad sequences for Higman's Lemma do not immediately apply.