##
**
Abelian Complexity Function of the Tribonacci Word
**

###
Ondřej Turek

Nuclear Physics Institute

Academy of Sciences of the Czech Republic

25068 Řež

Czech Republic

and

Bogolyubov Laboratory of Theoretical Physics

Joint Institute for Nuclear Research

141980 Dubna

Russia

**Abstract:**

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 *n* ∈ **N**.
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*))_{n∈N}
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**