The numbers of repeated palindromes in the Fibonacci and Tribonacci words

The Fibonacci word F is the fixed point beginning with a of morphism σ(a)=ab and σ(b)=a. Since F is uniformly recurrent, each factor ω appears infinitely many times in the sequence which is arranged as ωp (the pth occurrence of ω, p≥1). Here we distinguish ωp≠ωq if p≠q. In this paper, we give an algorithm for counting the number of repeated palindromes in F[1,n] (the prefix of F of length n). That is the number of the pairs (ω,p), where ω is a palindrome and ωp≺F[1,n]. We also get explicit expressions for some special n such as n=fm (the mth Fibonacci number). Similar results are also given for the Tribonacci word, the fixed point beginning with a of morphism τ(a)=ab, τ(b)=ac and τ(c)=a.