2019/11/27 by Ghareghani, Narges, Sharifani, Pouyeh, Mohammad-Noori, Morteza
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1911.12416
The Fibonacci word W on an infinite alphabet was introduced in [Zhang et al., Electronic J. Combinatorics 2017 24(2), 2-52] as a fixed point of the morphism 2i→ (2i)(2i+1), (2i+1) → (2i+2), i≥ 0. Here, for any integer k>2, we define the infinite k-bonacci word W(k) on the infinite alphabet as the fixed point of the morphism φk on the alphabet ℕ defined for any i≥ 0 and any 0≤ j≤ k-1, as φk(ki+j) = \ (ki)(ki+j+1) · amp; if j = 0,⋯ ,k-2,
(ki+j+1) · amp; otherwise. . We consider the sequence of finite words (W(k)n)n≥ 0, where W(k)n is the prefix of W(k) whose length is the (n+k)-th k-bonacci number. We then provide a recursive formula for the number of palindromes occur in different positions of W(k)n. Finally, we obtain the structure of all palindromes occurring in W(k) and based on this, we compute the palindrome complexity of W(k), for any k>2.