## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 313-337 |

Number of pages | 25 |

Journal | Mathematics in Computer Science |

Volume | 4 |

Issue number | 2-3 |

DOIs | |

State | Published - Sep 2010 |

## All Science Journal Classification (ASJC) codes

- Computational Mathematics
- Computational Theory and Mathematics
- Applied Mathematics

## Keywords

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