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 author 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\geq 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\leq k\leq 6$ have been calculated and reported in the Appendix. Some properties of $P_k$ are shown. In particular, broad upper and lower bounds for $P_k$, as well as for $\sum_{m=0}^n P_k(m)$ and $g_k$, are determined. Finally, some conjectures concerning the map $P_k$ are formulated.