  In this paper, we prove results on enumerations of sets of Rota-Baxter words
in a finite number of generators and a finite number of unary operators.
Rota-Baxter words are words formed by concatenating generators and images of
words under Rota-Baxter operators. Under suitable conditions, they form
canonical bases of free Rota-Baxter algebras and are studied recently in
relation to combinatorics, number theory, renormalization in quantum field
theory, and operads. Enumeration of a basis is often a first step to choosing a
data representation in implementation. Our method applies some simple ideas
from formal languages and compositions (ordered partitions) of an integer. We
first settle the case of one generator and one operator where both have
exponent 1 (the idempotent case). Some integer sequences related to these sets
of Rota-Baxter words are known and connected to other combinatorial sequences,
such as the Catalan numbers, and others are new. The recurrences satisfied by
the generating series of these sequences prompt us to discover an efficient
algorithm to enumerate the canonical basis of certain free Rota-Baxter
algebras. More general sets of Rota-Baxter words are enumerated with summation
techniques related to compositions of integers.
