TOPICS
Search

Squarefree Word


A "square" word consists of two identical adjacent subwords (for example, acbacb). A squarefree word contains no square words as subwords (for example, abcacbabcb). The only squarefree binary words are a, b, ab, ba, aba, and bab (since aa, bb, aaa, aab, abb, baa, bba, and bbb contain square identical adjacent subwords a, b, a, a, b, a, b, and b, respectively).

However, there are arbitrarily long ternary squarefree words. The number s(n) of ternary squarefree words of length n=1, 2, ... are 1, 3, 6, 12, 18, 30, 42, 60, ... (OEIS A006156), and s(n) is bounded by

 6·1.032^n<=s(n)<=6·1.379^n

(Brandenburg 1983). In addition,

 S=lim_(n->infty)[s(n)]^(1/n)=1.302...

(Brinkhuis 1983, Noonan and Zeilberger 1999).

The number of squarefree quaternary words of length n=1, 2, ... are 4, 12, 36, 96, 264, 696, ... (OEIS A051041).


See also

Alphabet, Cubefree Word, Overlapfree 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.Baake, M.; Elser, V.; and Grimm, U. "The Entropy of Square-Free Words." 8 Sep 1998. http://arxiv.org/abs/math-ph/9809010.Bean, D. R.; Ehrenfeucht, A.; and McNulty, G. F. "Avoidable Patterns in Strings of Symbols." Pacific J. Math. 85, 261-294, 1979.Berstel, J. and Reutenauer, C. "Square-Free Words and Idempotent Semigroups." In Combinatorics on Words (Ed. M. Lothaire). Reading, MA: Addison-Wesley, pp. 18-38, 1983.Brandenburg, F.-J. "Uniformly Growing kth 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.Crochemore, M. "Sharp Characterizations of Squarefree Morphisms." Theor. Comput. Sic. 18, 221-226, 1982.Crochemore, M. "Tests sur les morphismes faiblement sans carré." In Combinatorics on Words (Ed. L. J. Cummings). Toronto: Academic Press, pp. 63-89, 1983.Finch, S. R. "Pattern-Free Word Constants." §5.17 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 367-371, 2003.Kobayashi, Y. "Repetition-Free Words." Theor. Comput. Sci. 44, 175-197, 1986.Leconte, M. "kth Power-Free Codes." In Automata on Infinite Words (Ed. M. Nivat and D. Perrin). Berlin: Springer-Verlag, pp. 172-178, 1985.Noonan, J. and Zeilberger, D. "The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations." J. Differ. Eq. Appl. 5, 355-377, 1999.Pleasants, P. A. B. "Nonrepetitive Sequences." Proc. Cambridge Philos. Soc. 68, 267-274, 1970.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.Sloane, N. J. A. Sequences A006156/M2550 and A051041 in "The On-Line Encyclopedia of Integer Sequences."Thue, A. "Über unendliche Zeichenreihen." Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana 7, 1-22, 1906. Reprinted in Nagell, T.; Selberg, A.; Selberg, S.; and Thalberg, K. (Eds.). Selected Mathematical Papers of Axel Thue. Oslo, Norway: Universitetsforlaget, pp. 139-158, 1977.Thue, A. "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen." Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana 1, 1-67, 1912. Reprinted in Nagell, T.; Selberg, A.; Selberg, S.; and Thalberg, K. (Eds.). Selected Mathematical Papers of Axel Thue. Oslo, Norway: Universitetsforlaget, pp. 413-477, 1977.

Referenced on Wolfram|Alpha

Squarefree Word

Cite this as:

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

Subject classifications