<p>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 <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibrep.html#zeck" rel="nofollow">Zeckendorf representation</a>.</p>

<p>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$.</p>

<p>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$.</p>

<p>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|$. </p>

<p>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$.</p>

<p>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}</p>

<p>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 <a href="http://www.wolframalpha.com/input/?i=f%28k%29=l%2af%28k-1%29%2bf%28k-2%29,%20f%280%29=1,%20f%281%29=l" rel="nofollow">Wolfram Alpha</a>. However, with a little bit of googling and poking around in <a href="http://oeis.org" rel="nofollow">OEIS</a>, we find that we actually have:
$$f(k) = U_k(l/2)$$
where $U_k$ is the $k^{th}$ <a href="http://en.wikipedia.org/wiki/Chebyshev_polynomials#Definition" rel="nofollow">Chebyshev polynomial of the second kind</a> (!).</p>

CC BY-SA 3.0
2011-08-21T16:49:44.527Z
That's very interesting, thank you.
Aaron Sterling
CC BY-SA 3.0
2011-08-21T16:14:36.683Z
2011-08-24T07:11:21.080Z
2011-08-24T07:11:21.080Z
mhum
<p>A completely different approach for the first question reuses the answers to the recent question on <a href="https://cstheory.stackexchange.com/q/7857/609">generating words in a regular language</a>: 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.</p>

CC BY-SA 3.0
2011-08-22T17:28:43.833Z
Thanks.  I was wondering if there might be a connection, and your answer here gave me the push I needed to look at the papers referenced there, and one of them definitely solves a piece of one of the problems I am considering.
Aaron Sterling
CC BY-SA 3.0
2011-08-22T09:57:03.203Z
2011-08-22T09:57:03.203Z
2017-04-13T12:32:28.167Z
Sylvain
<p>Updated: this answer is <strong>incorrect</strong>: </p>

<p>assuming $j$ is fixed, we can count the number of <em>ways</em> 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 <strong>not</strong> 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.</p>

<hr>

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

<ul>
<li>either $a$ the first symbol never appears, which accounts for $(l-1)^k$ possible words,</li>
<li>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.</li>
</ul>

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

CC BY-SA 3.0
2011-08-19T20:57:44.003Z
Thanks very much, Sylvain, though I don't think that's quite right.  We can use $b$ later in the word if $a$ appears.  We just can't use $b$ if there are exactly $j$ letters in between $a$ and $b$, if $a \lozenge ^j b$ appeared earlier.  Perhaps I am misunderstanding your argument though.
Aaron Sterling
CC BY-SA 3.0
2011-08-19T21:04:23.787Z
Sorry, I wasn't sure whether $j$ was fixed or not.  I've edited the answer with fixed $j$ as well.
Sylvain
CC BY-SA 3.0
2011-08-20T13:09:46.630Z
I do not think that the fixed-j case is correct.  For example, if k=4 and j=1, the word aabb is subtracted twice.  I haven’t read the non-fixed-j case.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-20T15:39:03.287Z
@Tsuyoshi Ito: you're right, there is no unique match in that case.
Sylvain
CC BY-SA 3.0
2011-08-20T17:42:24.877Z
Please mark an incorrect answer as such.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-21T14:08:59.570Z
I did the same mistake. Maybe this approach can be fixed by applying the inclusion–exclusion principle?
Raphael
CC BY-SA 3.0
2011-08-22T09:56:53.283Z
@Raphael: yes, I started thinking along these lines, but then I found the expressions for overlapping patterns to be quite annoyingly complex.
Sylvain
CC BY-SA 3.0
2011-08-19T20:41:31.310Z
2011-08-24T19:59:45.163Z
2011-08-24T19:59:45.163Z
Sylvain
<p><strong>EDITED TO ADD</strong>: This question is now essentially answered; please see <a href="http://wp.me/p1mOPD-7y" rel="nofollow noreferrer">this blog entry</a> for more details.  Thanks to everyone who posted comments and answers here.</p>

<hr>

<p><strong>ORIGINAL QUESTION</strong></p>

<p>This is a hopefully smarter and better-informed version of a <a href="https://mathoverflow.net/questions/72776/is-there-an-official-name-for-this-prohibited-word-pattern">question I asked</a> 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 <a href="http://rads.stackoverflow.com/amzn/click/1420060929" rel="nofollow noreferrer">here</a>.)</p>

<p>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$.)</p>

<p>Example where $k=4$ and $l=5$:</p>

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

<p>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:</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>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:</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>Thanks.</p>

CC BY-SA 3.0
2011-08-19T15:44:12.787Z
(1) I cannot understand the correspondence between your first question and the example stated before it.  What is the input in your example?  (2) In your first question, are you using k for two different purposes?
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-19T15:51:33.607Z
Regarding (2), yes I made a mistake, now edited, thank you.
Aaron Sterling
CC BY-SA 3.0
2011-08-19T15:53:10.313Z
Regarding (1), I would like to know "how much room I have left" once a partial word appears.  But yes, the real question is how to produce lists like the one that appears in the example (without the prohibited partial words).  So the input would be the values of $k$ and $l$, and a desired number of words to produce in a list, all of which had the "avoidance of previously appearing partial words property."
Aaron Sterling
CC BY-SA 3.0
2011-08-19T16:21:27.463Z
I still do not get it.  You state in the question that you are given a partial word of form $a \lozenge^j b$, but you only state k and l in the example.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-19T16:31:30.187Z
@Tsuyoshi: I'm grateful for the attention, but I am afraid I don't get what you don't get. $j \leq k-2$, and that particular question is: how many words of length $k$ on $l$ letters avoid $a \lozenge^jb$ where $a,b$ are in the alphabet, and maybe $a=b$? That seems like an "easy" calculation though, and really it's the warmup for finding lists whose entries have to avoid progressively many such words.
Aaron Sterling
CC BY-SA 3.0
2011-08-19T16:44:40.770Z
@Aaron, I don't know what your ultimate application is, but Davenport-Schinzel sequences (and generalizations) ask about the maximum length of a string that does not contain a particular repeating pattern. It's a related notion.
Suresh Venkat
CC BY-SA 3.0
2011-08-19T20:02:07.203Z
@Suresh: Thank you.  I have seen those before, in passing.  Maybe it's time I actually paid attention to them.
Aaron Sterling
CC BY-SA 3.0
2011-08-19T20:12:22.593Z
Seth Pettie has been studying some very nifty generalizations to forbidden submatrices as well.
Suresh Venkat
<co.combinatorics>
How many words of length $k$ on $l$ letters avoid a partial word?
Aaron Sterling
# How many words of length $k$ on $l$ letters avoid a partial word?

(Asked by: username_0 on 2011-08-19)

**EDITED TO ADD**: This question is now essentially answered; please see [this blog entry](http://wp.me/p1mOPD-7y) 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](https://mathoverflow.net/questions/72776/is-there-an-official-name-for-this-prohibited-word-pattern) 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](http://rads.stackoverflow.com/amzn/click/1420060929).)

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.

**Tags:** co.combinatorics
> **Comments:**
> **username_1**: (1) I cannot understand the correspondence between your first question and the example stated before it.  What is the input in your example?  (2) In your first question, are you using k for two different purposes?  
> **username_0**: Regarding (2), yes I made a mistake, now edited, thank you.  
> **username_0**: Regarding (1), I would like to know "how much room I have left" once a partial word appears.  But yes, the real question is how to produce lists like the one that appears in the example (without the prohibited partial words).  So the input would be the values of $k$ and $l$, and a desired number of words to produce in a list, all of which had the "avoidance of previously appearing partial words property."  
> **username_1**: I still do not get it.  You state in the question that you are given a partial word of form $a \lozenge^j b$, but you only state k and l in the example.  
> **username_0**: @Tsuyoshi: I'm grateful for the attention, but I am afraid I don't get what you don't get. $j \leq k-2$, and that particular question is: how many words of length $k$ on $l$ letters avoid $a \lozenge^jb$ where $a,b$ are in the alphabet, and maybe $a=b$? That seems like an "easy" calculation though, and really it's the warmup for finding lists whose entries have to avoid progressively many such words.  
> **username_2**: @Aaron, I don't know what your ultimate application is, but Davenport-Schinzel sequences (and generalizations) ask about the maximum length of a string that does not contain a particular repeating pattern. It's a related notion.  
> **username_0**: @Suresh: Thank you.  I have seen those before, in passing.  Maybe it's time I actually paid attention to them.  
> **username_2**: Seth Pettie has been studying some very nifty generalizations to forbidden submatrices as well.  

---

## 3 answers

### Answer by username_3 on 2011-08-21. Score: 4 | Accepted answer

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](http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibrep.html#zeck).

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](http://www.wolframalpha.com/input/?i=f%28k%29=l%2af%28k-1%29%2bf%28k-2%29,%20f%280%29=1,%20f%281%29=l). However, with a little bit of googling and poking around in [OEIS](http://oeis.org), 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](http://en.wikipedia.org/wiki/Chebyshev_polynomials#Definition) (!).

> **Comments:**
> **username_0**: That's very interesting, thank you.  

---

### Answer by username_4 on 2011-08-22. Score: 2

A completely different approach for the first question reuses the answers to the recent question on [generating words in a regular language](https://cstheory.stackexchange.com/q/7857/609): 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.

> **Comments:**
> **username_0**: Thanks.  I was wondering if there might be a connection, and your answer here gave me the push I needed to look at the papers referenced there, and one of them definitely solves a piece of one of the problems I am considering.  

---

### Answer by username_4 on 2011-08-19. Score: 0

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.

> **Comments:**
> **username_0**: Thanks very much, Sylvain, though I don't think that's quite right.  We can use $b$ later in the word if $a$ appears.  We just can't use $b$ if there are exactly $j$ letters in between $a$ and $b$, if $a \lozenge ^j b$ appeared earlier.  Perhaps I am misunderstanding your argument though.  
> **username_4**: Sorry, I wasn't sure whether $j$ was fixed or not.  I've edited the answer with fixed $j$ as well.  
> **username_1**: I do not think that the fixed-j case is correct.  For example, if k=4 and j=1, the word aabb is subtracted twice.  I haven’t read the non-fixed-j case.  
> **username_4**: @Tsuyoshi Ito: you're right, there is no unique match in that case.  
> **username_1**: Please mark an incorrect answer as such.  
> **username_5**: I did the same mistake. Maybe this approach can be fixed by applying the inclusion–exclusion principle?  
> **username_4**: @Raphael: yes, I started thinking along these lines, but then I found the expressions for overlapping patterns to be quite annoyingly complex.  

---

