On the 2-binomial complexity of the generalized Thue-Morse words

Abstract

In this paper, we study the $2$-binomial complexity $b_{{\mathbf{t}}_m,2}(n)$ of the generalized Thue-Morse words ${\mathbf{t}}_m$ for every integer $m\ge 3$. We obtain the exact value of $b_{{\mathbf{t}}_m,2}(n)$ for every integer $n\ge m^2$. As a consequence, $b_{{\mathbf{t}}_m,2}(n)$ is ultimately periodic with period $m^2$. This result partially answers a question of M. Lejeune, J. Leroy and M. Rigo [Computing the $k$-binomial complexity of the Thue-Morse word, J. Comb. Theory Ser. A, {\bf 176} (2020) 105284].

18 pages