Journal of Integer Sequences, Vol. 19 (2016), Article 16.6.7

An Improved Lower Bound on the Number of Ternary Squarefree Words

Michael Sollami
Ditto Labs, Inc.
1 Broadway, 14th Floor
Cambridge, MA 02142

Craig C. Douglas
University of Wyoming
School of Energy Resources and Department of Mathematics
1000 E. University Ave., Dept. 3036
Laramie, WY 82072

Manfred Liebmann
Technische Universität München
Center for Mathematical Sciences
Boltzmannstraße 3
85748 Garching bei München


Let sn be the number of words in the ternary alphabet Σ = {0, 1, 2} such that no subword (or factor) is a square (a word concatenated with itself, e.g., 11, 1212, and 102102). From computational evidence, the sequence (sn) grows exponentially at a rate of about 1.317277n. While known upper bounds are already relatively close to the conjectured rate, effective lower bounds are much more difficult to obtain. In this paper, we construct a 54-Brinkhuis 952-triple, which leads to an improved lower bound on the number of n-letter ternary squarefree words: 952n/53 ≈ 1.1381531n.

Full version:  pdf,    dvi,    ps,    latex    

Accompanying files:   b0.txt,      b1.txt,      b2.txt,      code.tgz   

(Concerned with sequences A006156 A010060.)

Received March 14 2016; revised version received May 5 2016; June 9 2016. Published in Journal of Integer Sequences, July 6 2016.

Return to Journal of Integer Sequences home page