Improved bounds on the number of ternary square-free words

Grimm, Uwe (2001). Improved bounds on the number of ternary square-free words. Journal of Integer Sequences, 4(2), article no. 01.2.7.

URL: http://www.cs.uwaterloo.ca/journals/JIS/VOL4/GRIMM...

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 65n/40, replacing the previous best lower bound of 2n/17.

Viewing alternatives

Download history

Item Actions

Export

About