Improved bounds on the number of ternary square-free words
Uwe Grimm · Open Research Online (The Open University) · 2001
Abstract. Improved upper and lower bounds on the number of squarefree 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. 1.