Some properties of $k$-bonacci words on infinite alphabet

Abstract

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\to (2i)(2i+1)$, $(2i+1)\to (2i+2)$, $i\ge 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 ${\phi }_k$ on the alphabet $\mathbb{N}$ defined for any $i\ge 0$ and any $0\le j\le k-1$, as \begin{equation*} φ_k(ki+j) = \left\{ \begin{array}{ll} (ki)(ki+j+1) & \text{if } j = 0,\cdots ,k-2,\\ (ki+j+1)& \text{otherwise}. \end{array} \right. \end{equation*} We consider the sequence of finite words $(W_n^{(k)}{)}_{n\ge 0}$, where $W_n^{(k)}$ 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_n^{(k)}$. 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$.