Journal of Integer Sequences, Vol. 4 (2001), Article 01.2.7

Improved Bounds on the Number of Ternary Square-Free Words

Uwe Grimm

Applied Mathematics Department
Faculty of Mathematics and Computing
The Open University, Walton Hall
Milton Keynes MK7 6AA, UK

Abstract: Improved upper and lower bounds on the number of square-free ternary words are obtained. The upper bound is based on the enumeration of square-free ternary words up to length 110. The lower bound is derived by constructing generalised Brinkhuis triples. The problem of finding such triples can essentially be reduced to a combinatorial problem, which can efficiently be treated by computer. In particular, it is shown that the number of square-free ternary words of length n grows at least as 65^{n/40}, replacing the previous best lower bound of 2^{n/17}.

(Mentions sequence A006156 .)

Received August 1, 2001; revised version received October 1, 2001. Published in Journal of Integer Sequences February 13, 2002.