Grimm, Uwe

Improved bounds on the number of ternary square-free words

J. Integer Seq. 4(2), Art. 01.2.7, 14 p., electronic only (2001)

Summary

Summary: 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.

Downloads