*N.B. A detailed on-line essay by S. Finch
was the starting point for this entry.*

A finite sequence of letters from some Alphabet is said to be an -ary word. A ``square'' word consists of
two identical subwords (for example, *acbacb*). A squarefree word contains *no* square words as subwords (for
example, *abcacbabcb*). The only squarefree binary words are , , *ab*, *ba*, *aba*, and *bab*.
However, there are arbitrarily long ternary squarefree words. The number of ternary squarefree words of length is
bounded by

(1) |

(2) |

(3) |

A word is said to be overlapfree if it has no subwords of the form *xyxyx*. A squarefree word is overlapfree, and an
overlapfree word is cubefree. The number of binary overlapfree words of length satisfies

(4) |

(5) |

(6) |

(7) | |||

(8) |

(Cassaigne 1993).

**References**

Brandenburg, F.-J. ``Uniformly Growing th Power-Free Homomorphisms.'' *Theor. Comput. Sci.* **23**, 69-82, 1983.

Brinkhuis, J. ``Non-Repetitive Sequences on Three Symbols.'' *Quart. J. Math. Oxford Ser. 2* **34**, 145-149, 1983.

Cassaigne, J. ``Counting Overlap-Free Binary Words.''
*STACS '93: Tenth Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 25-27, 1993 Proceedings*
(Ed. G. Goos, J. Hartmanis, A. Finkel, P. Enjalbert, K. W. Wagner). New York: Springer-Verlag, pp. 216-225, 1993.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/words/words.html

Kobayashi, Y. ``Enumeration of Irreducible Binary Words.'' *Discrete Appl. Math.* **20**, 221-232, 1988.

Noonan, J. and Zeilberger, D. ``The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations.'' Submitted.

© 1996-9

1999-05-26