Combinatorial objects such as rooted trees that carry a recursive structure
have found important applications recently in both mathematics and physics. We
put such structures in an algebraic framework of operated semigroups. This
framework provides the concept of operated semigroups with intuitive and
convenient combinatorial descriptions, and at the same time endows the familiar
combinatorial objects with a precise algebraic interpretation. As an
application, we obtain constructions of free Rota-Baxter algebras in terms of
Motzkin paths and rooted trees.