Enumeration and Generating Functions of Rota-Baxter Words

Li Guo, William Y. Sit

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


In this paper, we prove results on enumerations of sets of Rota-Baxter words (RBWs) in a single generator and one unary operator. Examples of operators are integral operators, their generalization to Rota-Baxter operators, and Rota-Baxter type operators. RBWs are certain words formed by concatenating generators and images of words under the operators. Under suitable conditions, they form canonical bases of free Rota-Baxter type algebras which are studied recently in relation to renormalization in quantum field theory, combinatorics, number theory, and operads. Enumeration of a basis is often a first step to choosing a data representation in implementation. We settle the case of one generator and one operator, starting with the idempotent case (more precisely, the exponent 1 case). Some integer sequences related to these sets of RBWs are known and connected to other sequences from combinatorics, 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.

Original languageEnglish (US)
Pages (from-to)313-337
Number of pages25
JournalMathematics in Computer Science
Issue number2-3
StatePublished - Sep 2010

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Computational Theory and Mathematics
  • Applied Mathematics


  • Catalan numbers
  • Compositions
  • Enumerative combinatorics
  • Generating functions
  • Grammar
  • Rota-Baxter algebras
  • Rota-Baxter words


Dive into the research topics of 'Enumeration and Generating Functions of Rota-Baxter Words'. Together they form a unique fingerprint.

Cite this