Journal of Integer Sequences, Vol. 18 (2015), Article 15.3.4

Abelian Complexity Function of the Tribonacci Word

Ondřej Turek
Nuclear Physics Institute
Academy of Sciences of the Czech Republic
25068 Řež
Czech Republic
Bogolyubov Laboratory of Theoretical Physics
Joint Institute for Nuclear Research
141980 Dubna


According to a result of Richomme, Saari and Zamboni, the abelian complexity of the Tribonacci word satisfies ρab(n) ∈ {3, 4, 5, 6, 7} for each nN. In this paper we derive an automaton that evaluates the function ρab(n) explicitly. The automaton takes the Tribonacci representation of n as its input; therefore, (ρab(n))nN is an automatic sequence in a generalized sense. Since our evaluation of ρab(n) uses O(log n) operations, it is fast even for large values of n. Our result also leads to a solution of an open problem proposed by Richomme et al. concerning the characterization of those n for which ρab(n) = c with c belonging to {4, 5, 6, 7}. In addition, we apply the same approach on the 4-bonacci word. In this way we find a description of the abelian complexity of the 4-bonacci word, too.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000073 A000078 A080843 A216190 A254990 A255014.)

Received October 7 2014; revised version received February 12 2015. Published in Journal of Integer Sequences, February 14 2015.

Return to Journal of Integer Sequences home page