Article

Enumeration of Rota-Baxter words

Authors:

William Y. SitAuthors Info & Claims

ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

Pages 124 - 131

https://doi.org/10.1145/1145768.1145793

Published: 09 July 2006 Publication History

Abstract

We describe 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.

References

[1]

Aguiar, M., 2000. Prepoisson algebras, Letters in Mathematical Physics, 54 (4), 263--277.

[2]

Aguiar, M., Moreira, W., 2005. Combinatorics of the free Baxter algebra, arXiv:math.CO/0510169.

[3]

Baxter, G., 1960. An analytic problem whose solution follows from a simple algebraic identity, Pacific J. Math. 10, 731--742.

[4]

Cartier, P., 1972. On the structure of free Baxter algebras, Adv. Math. 9, 253--265.

[5]

Connes, A., Kreimer, D., 2000. Renormalization in quantum field theory and the Riemann-Hilbert problem. I. The Hopf algebra structure of graphs and the main theorem, Comm. Math. Phys., 210, 249--273.

[6]

Connes, A., Kreimer, D., 2001. Renormalization in quantum field theory and the Riemann-Hilbert problem. II. The β-function, diffeomorphisms and the renormalization group, Comm. Math. Phys., 216 (1), 215--241.

[7]

Ebrahimi-Fard, K., 2001. Loday-type algebras and the Rota-Baxter relation, Lett. Math. Phys., 61, 139--147.

[8]

Ebrahimi-Fard, K., Guo, L., 2004. Free Rota-Baxter algebras, dendriform algebras and Poicaré-Birkhoff-Witt theorem, arXiv:math.RA/0503647.

[9]

Ebrahimi-Fard, E., Guo, L., 2005. On free Rota-Baxter algebras, arXiv: math.RA/0510266.

[10]

Ebrahimi-Fard, E., Guo, L., 2006. Multiple zeta values and Rota-Baxter algebras, arXiv:math.NT/0601558.

[11]

Ebrahimi-Fard, K., Guo, L., Kreimer, D., 2005. Integrable renormalization II: the general case, Annales Henri Poincare, 6, 369--395.

[12]

Ebrahimi-Fard, K., Guo, L., Kreimer, D., 2004. Spitzer's identity and the algebraic Birkhoff decomposition in pQFT, J. Phys. A: Math. Gen. 37, 11037--11052.

[13]

Guo, L., 2005. Baxter algebras, Stirling numbers and partitions, J. Algebra Appl. 4, 153--164.

[14]

Guo, L., Keigher, W., 2000. Baxter algebras and shuffle products, Adv. Math., 150, 117--149.

[15]

Guo, L., Keigher, W., 2000. On free Baxter algebras: completions and the internal construction, Adv. in Math., 151, 101--127.

[16]

Guo, L., Sit, W. Y., 2006. Enumeration of Rota-Baxter words (full version), arXiv:math.RA/0602449.

[17]

Loday, J.-L., 2001. Dialgebras, in Dialgebras and related operads, Lecture Notes in Math., vol. 1763, Springer, New York, pp. 7--66.

[18]

MacMahon, M. P. A., 1984. Combinatory Analysis. Chelsea Pub. Co., New York, third edition.

[19]

Nijenhuis, A., Wilf, H., 1978. Combinatorial Algorithms, Academic Press, second edition.

[20]

Rota, G.-C., 1969. Baxter algebras and combinatorial identities I, II, Bull. Amer. Math. Soc. 75, 325--329, 330--334.

[21]

Rota, G.-C., 1995. Baxter operators, an introduction, In: Gian-Carlo Rota on Combinatorics, Introductory Papers and Commentaries, Joseph P.S. Kung, Editor, Birkhäuser, Boston.

[22]

Rota, G.-C., Smith, D. A., 1972. Fluctuation theory and Baxter algebras, Istituto Nazionale di Alta Matematica, IX, 179--201.

[23]

Sloane, N., On-Line Encyclopedia of Integer Seqences, www.research.att.com/~njas/sequences/index.html

Cited By

Qi ZQin YWang KZhou G(2021)Free objects and Gröbner-Shirshov bases in operated contextsJournal of Algebra10.1016/j.jalgebra.2021.04.042Online publication date: Jun-2021
https://doi.org/10.1016/j.jalgebra.2021.04.042
Guo LSit WZhang R(2013)Differential type operators and Gröbner-Shirshov basesJournal of Symbolic Computation10.1016/j.jsc.2012.05.01452(97-123)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.jsc.2012.05.014
Guo LSit WZhang RSchost ÉEmiris I(2011)On Rota's problem for linear operators in associative algebrasProceedings of the 36th international symposium on Symbolic and algebraic computation10.1145/1993886.1993912(147-154)Online publication date: 8-Jun-2011
https://dl.acm.org/doi/10.1145/1993886.1993912
Show More Cited By

Index Terms

Enumeration of Rota-Baxter words

Recommendations

Monads and distributive laws for Rota-Baxter and differential algebras

In recent years, algebraic studies of the differential calculus and integral calculus in the forms of differential algebra and Rota-Baxter algebra have been merged together to reflect the close relationship between the two calculi through the First ...
Typed angularly decorated planar rooted trees and generalized Rota–Baxter algebras
Abstract
We introduce a generalization of parametrized Rota–Baxter algebras, named $Ω$ -Rota–Baxter algebra, which includes family and matching Rota–Baxter algebras. We study the structure needed on the set $Ω$ of parameters in order to obtain that free $Ω$ -Rota–...
Hopf algebra structure on free Rota–Baxter algebras by angularly decorated rooted trees
Abstract
By means of a new notion of subforests of an angularly decorated rooted forest, we give a combinatorial construction of a coproduct on the free Rota–Baxter algebra on angularly decorated rooted forests. We show that this coproduct equips the Rota–...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

July 2006

374 pages

ISBN:1595932763

DOI:10.1145/1145768

General Chair:
Barry Trager
IBM T.J. Watson Research Center, USA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 July 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC06

Sponsor:

ISSAC06: International Symposium on Symbolic and Algebraic Computation

July 9 - 12, 2006

Genoa, Italy

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
127
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Qi ZQin YWang KZhou G(2021)Free objects and Gröbner-Shirshov bases in operated contextsJournal of Algebra10.1016/j.jalgebra.2021.04.042Online publication date: Jun-2021
https://doi.org/10.1016/j.jalgebra.2021.04.042
Guo LSit WZhang R(2013)Differential type operators and Gröbner-Shirshov basesJournal of Symbolic Computation10.1016/j.jsc.2012.05.01452(97-123)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.jsc.2012.05.014
Guo LSit WZhang RSchost ÉEmiris I(2011)On Rota's problem for linear operators in associative algebrasProceedings of the 36th international symposium on Symbolic and algebraic computation10.1145/1993886.1993912(147-154)Online publication date: 8-Jun-2011
https://dl.acm.org/doi/10.1145/1993886.1993912
Guo LSit W(2011)Enumeration and Generating Functions of Rota–Baxter WordsMathematics in Computer Science10.1007/s11786-010-0061-24:2-3(313-337)Online publication date: 11-Jan-2011
https://doi.org/10.1007/s11786-010-0061-2

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents