Enumeration and Generating Functions of Differential Rota-Baxter Words

Li Guo, William Y. Sit

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


In this paper, the methods and results in enumeration and generation of Rota-Baxter words in Guo and Sit (Algebraic and Algorithmic Aspects of Differential and Integral Operators (AADIOS), Math. Comp. Sci., vol. 4, Sp. Issue (2,3), 2011) are generalized and applied to a free, non-commutative, non-unitary, ordinary differential Rota-Baxter algebra with one generator. A differential Rota-Baxter algebra is an associative algebra with two operators modeled after the differential and integral operators, which are related by the First Fundamental Theorem of Calculus. Differential Rota-Baxter words are words formed by concatenating differential monomials in the generator with images of words under the Rota-Baxter operator. Their totality is a canonical basis of a free, non-commutative, non-unitary, ordinary differential Rota-Baxter algebra. A free differential Rota-Baxter algebra can be constructed from a free Rota-Baxter algebra on a countably infinite set of generators. The order of the derivation gives another dimension of grading on differential Rota-Baxter words, enabling us to generalize and refine results from Guo and Sit to enumerate the set of differential Rota-Baxter words and outline an algorithm for their generation according to a multi-graded structure. Enumeration of a basis is often a first step to choosing a data representation in implementation of algorithms involving free algebras, and in particular, free differential Rota-Baxter algebras and several related algebraic structures on forests and trees. The generating functions obtained can be used to provide links to other combinatorial structures.

Original languageEnglish (US)
Pages (from-to)339-358
Number of pages20
JournalMathematics in Computer Science
Issue number2-3
StatePublished - Sep 2010

ASJC Scopus subject areas

  • Computational Mathematics
  • Computational Theory and Mathematics
  • Applied Mathematics


  • Colorings
  • Compositions
  • Differential Rota-Baxter algebras
  • Differential Rota-Baxter words
  • Enumerative combinatorics
  • Generating functions


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

Cite this