tailieunhanh - Báo cáo toán học: "On the Entropy and Letter Frequencies of Ternary Square-Free Words"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: On the Entropy and Letter Frequencies of Ternary Square-Free Words. | On the Entropy and Letter Frequencies of Ternary Square-Free Words Christoph Richard Institut fur Mathematik Universitat Greifswald Jahnstr. 15a 17487 Greifswald Germany richard@ Uwe Grimm Applied Mathematics Department The Open University Walton Hall Milton Keynes MK7 6AA UK Submitted Mar 19 2003 Accepted Aug 28 2003 Published Feb 14 2004 Keywords Combinatorics on words square-free words Mathematics Subject Classifications 68R15 05A15 Abstract We enumerate ternary length- square-free words which are words avoiding squares of all words up to length I for I 24. We analyse the singular behaviour of the corresponding generating functions. This leads to new upper entropy bounds for ternary square-free words. We then consider ternary square-free words with fixed letter densities thereby proving exponential growth for certain ensembles with various letter densities. We derive consequences for the free energy and entropy of ternary square-free words. 1 Introduction The interest in the combinatorics of pattern-avoiding 3 2 8 in particular of power-free words goes back to work of Axel Thue in the early 20th century 37 38 . The celebrated Prouhet-Thue-Morse sequence defined by a substitution rule a ab and b ba on a two-letter alphabet a b proves the existence of infinite cube-free words in two letters a and b. Here a word of length n is a string of n letters from a certain alphabet E an element of the set En of n-letter words in E. The union E un 0 En is the language of all words in the alphabet E. It is a monoid with concatenation of words as operation and with the empty word A of zero length as neutral element 23 in particular E0 A . A word w is called square-free if w xyyz with words x y and z implies that y A is the empty word and cube-free words are defined analogously. So square-free words are characterised by the property that they do not contain an adjacent repetition of any subword. THE ELECTRONIC JOURNAL OF COMBINATORICS 11 .