The numbers of repeated palindromes in the Fibonacci and Tribonacci words (Q2399293)

The Fibonacci word \(F\) is the fixed point beginning with \(a\) of the morphism \(\sigma(a)=ab\) and \(\sigma(b)=a\). Similarly, the Tribonacci word \(T\) is the fixed point beginning with \(a\) of the morphism \(\tau(a)=ab\), \(\tau(b)=ac\) and \(\tau(c)=a\). Let \(F[1, n]\) (resp. \(T[1, n]\)) be the prefix of \(F\) (resp. \(T\)) of length \(n\). A palindrome is a finite word that reads the same backwards as forwards. From previous studies the number of distinct palindromes in \(F[1, n]\) (resp. \(T[1, n]\)) is \(n + 1\) for all \(n\). In the present paper the authors consider the numbers of repeated palindromes in \(F[1, n]\) and \(T[1, n]\). Using the ``gap sequence'' properties of \(F\) and \(T\), which were introduced and studied by the same authors, they determine the positions of all occurrences for all palindromes, give an algorithm for counting the number of repeated palindromes in \(F[1, n]\) and \(T[1, n]\), and also get explicit expressions for some special \(n\). The research on counting the repeated palindromes is not rich. To the best of our knowledge it seems that the authors are the first to study this problem on the Fibonacci and Tribonacci words. The paper's approach for counting the repeated palindromes seems suitable for the \(m\)-bonacci word, and even suitable for Sturmian sequences, episturmian sequences etc., if the ``gap sequence'' properties of them are found.