TOPICS
Search

Overlapfree Word

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 t(n) of binary overlapfree words of length n=1, 2, ... are 2, 4, 6, 10, 14, 20, ... (OEIS A007777). t(n) satisfies

p·n^(1.155)<=t(n)<=q·n^(1.587)
(1)

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

lim_(n->infty)(lnt(n))/(lnn)
(2)

does not exist,

1.155<T_L<1.276<1.332<T_U<1.587,
(3)

where

T_L=liminf_(n->infty)(lnt(n))/(lnn)
(4)
T_U=limsup_(n->infty)(lnt(n))/(lnn)
(5)

(Cassaigne 1993).

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

See also

Cubefree Word, Squarefree Word, Word

Explore with Wolfram|Alpha

References

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."

Referenced on Wolfram|Alpha

Overlapfree Word

Cite this as:

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

Subject classifications