On the number of episturmian palindromes
Episturmian words are a suitable generalization to arbitrary alphabets of Sturmian words. In this paper we are interested in the problem of enumerating the palindromes in all episturmian words over a k-letter alphabet A(k). We give a formula for the map g(k) giving for any n the number of all palindromes of length n in all episturmian words over A(k). This formula extends to k > 2 a similar result obtained for k = 2 by the second and third authors in 2006. The map g(k) is expressed in terms of the map P(k) counting for each n the palindromic prefixes of all standard episturmian words (epicentral words). For any n >= 0, P(2)(n) = phi(n + 2), where phi is the totient Euler function. The map P(k) plays an essential role also in the enumeration formula for the map lambda(k) counting for each n the finite episturmian words over A(k). Similarly to Euler's function, the behavior of P(k) is quite irregular. The first values of P(k) and of the related maps g(k), and lambda(k) for 3 <= k <= 6 have been calculated and reported in the paper. Some properties of P(k) are shown. In particular, broad upper and lower bounds for P(k), as well as for Sigma(n)(m=0) P(k)(m) and g(k), are determined. Finally, some conjectures concerning the map P(k) are formulated. (C) 2010 Elsevier B.V. All rights reserved.
palindromes episturmian words sturmian words epicentral words palindromization map