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 numbers of binary overlapfree words of length , 2, ... are 2, 4, 6, 10, 14, 20, ... (Sloane's A007777). satisfies

(1)

for some constants and (Restivo and Selemi 1985, Kobayashi 1988). In addition, while

(2)

does not exist,

(3)

where

			(4)
			(5)

(Cassaigne 1993).

The Thue-Morse sequence is overlapfree (Allouche and Shallit 2003, p. 15).

Allouche, J.-P. and Shallit, J. "Repetition in Words." §1.6 in Automatic Sequences: Theory, Applications, Generalizations. Cambridge, England: Cambridge University Press, pp. 14-16, 2003.

Cassaigne, J. "Counting Overlap-Free Binary Words." In 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.

Cassaigne, J. Motifs évitables et régularités dans les mots (Thèse de Doctorat). Tech. Rep. LITP-TH 94-04. Paris: Institut Blaise Pascal, 1994.

Finch, S. R. "Pattern-Free Word Constants." §5.17 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 367-371, 2003.

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

Restivo, A. and Salemi, S. "Overlap-Free Words on Two Symbols." In Automata on Infinite Words (Ed. M. Nivat and D. Perrin). New York: Springer-Verlag, pp. 198-206, 1985.

Séébold, P. "Overlap-Free Sequences." In Combinatorics on Words (Ed. L. J. Cummings). Toronto: Academic Press, pp. 207-215, 1983.

Sloane, N. J. A. Sequence A007777 in "The On-Line Encyclopedia of Integer Sequences."

CITE THIS AS:

Weisstein, Eric W. "Overlapfree Word." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/OverlapfreeWord.html