Improved bounds on the number of ternary square-free words
| dc.creator | Grimm, Uwe | |
| dc.date | 2001-05-29 | |
| dc.date | 2001-08-02 | |
| dc.date.accessioned | 2026-07-07T04:41:55Z | |
| dc.date.available | 2026-07-07T04:41:55Z | |
| dc.description | 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). | |
| dc.description | 17 pages, AMS LaTeX. Paper has been completely rewritten and comprises new results on both lower and upper bounds. The Mathematica program mentioned in the article can be downloaded at http://mcs.open.ac.uk/ugg2/wordcomb/brinkhuistriples.m | |
| dc.identifier | https://arxiv.org/abs/math/0105245 | |
| dc.identifier | http://arxiv.org/abs/math/0105245 | |
| dc.identifier | Journal of Integer Sequences, Vol. 4 (2001), Ar ticle 01.2.7 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/61556 | |
| dc.subject | Combinatorics | |
| dc.title | Improved bounds on the number of ternary square-free words | |
| dc.type | text |