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 Ak. We give a formula for the map gk giving for any n the number of all palindromes of length n in all episturmian words over Ak. This formula extends to k>2 a similar result obtained for k=2 by the second and third authors in 2006. The map gk is expressed in terms of the map Pk counting for each n the palindromic prefixes of all standard episturmian words (epicentral words). For any n≥0, P2(n)=φ(n+2), where φ is the totient Euler function. The map Pk plays an essential role also in the enumeration formula for the map λk counting for each n the finite episturmian words over Ak. Similarly to Euler’s function, the behavior of Pk is quite irregular. The first values of Pk and of the related maps gk, and λk for 3≤k≤6 have been calculated and reported in the paper. Some properties of Pk are shown. In particular, broad upper and lower bounds for Pk, as well as for and gk, are determined. Finally, some conjectures concerning the map Pk are formulated.