Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aguiar, M.: On the associative analog of Lie bialgebras. J. Algebra 244, 492–532 (2001)
Aguiar, M., Moreira, W.: Combinatorics of the free Baxter algebra. Electron. J. Comb. 13, R17 (2006). arXiv:math.CO/0510169
Alonso, L.: Uniform generation of a Motzkin word. Theor. Comput. Sci. 134, 529–536 (1994)
Baxter, G.: An analytic problem whose solution follows from a simple algebraic identity. Pac. J. Math. 10, 731–742 (1960)
Benchekroun, S., Moszkowski, P.: A new bijection between ordered trees and legal bracketings. Eur. J. Comb. 17, 605–611 (1996)
Bertrand, T.: Solution d’un problème. C.R. Acad. Sci. Paris 105, 369 (1887)
Cartier, P.: On the structure of free Baxter algebras. Adv. Math. 9, 253–265 (1972)
Chen, W.Y.C., Shapiro, L.W., Yang, L.L.M.: Parity reversing involutions on plane trees and 2-Motzkin paths. Eur. J. Comb. 27, 283–289 (2006)
Cohn, R.M.: Difference Algebra. Interscience, New York (1965)
Connes, A., Kreimer, D.: Hopf algebras, renormalization and noncommutative geometry. Commun. Math. Phys. 199, 203–242 (1998)
Diestel, R.: Graph Theory, 3rd edn. Springer, Berlin (2005). Available on-line: http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/download.html
Deutsch, E., Shapiro, L.W.: A bijection between ordered trees and 2-Motzkin paths and its many consequences. Discrete Math. 256, 655–670 (2002)
Donaghey, R., Shapiro, L.W.: Motzkin numbers. J. Comb. Theory Ser. A 23, 291–301 (1977)
Ebrahimi-Fard, K., Gracia-Bondia, J.M., Patras, F.: A Lie theoretic approach to renormalization. Commun. Math. Phys. 81, 61–75 (2007). arXiv:hep-th/0609035
Ebrahimi-Fard, K., Guo, L.: Rota–Baxter algebras and dendriform dialgebras. J. Pure Appl. Algebra (to appear). arXiv: math.RA/0503647
Ebrahimi-Fard, K., Guo, L.: Free Rota–Baxter algebras and rooted trees. J. Algebra Appl. (accepted). arXiv:math.RA/0510266
Ebrahimi-Fard, K., Guo, L., Kreimer, D.: Integrable renormalization II: the general case. Ann. Henri Poincare 6, 369–395 (2005)
Ebrahimi-Fard, K., Guo, L., Kreimer, D.: Spitzer’s identity and the algebraic Birkhoff decomposition in pQFT. J. Phys. A: Math. Gen. 37, 11037–11052 (2004)
Ebrahimi-Fard, K., Guo, L., Manchon, D.: Birkhoff type decompositions and the Baker-Campbell-Hausdorff recursion. Commun. Math. Phys. 267, 821–845 (2006)
Engel, K.-J., Nagel, R.: One-Parameter Semigroups for Linear Evolution Equations. Graduate Texts in Mathematics, vol. 194. Springer, New York (2000)
Flajolet, P.: Mathematical methods in the analysis of algorithms and data structures. In: Trends in Theoretical Computer Science, Udine, 1984. Principles Comput. Science Ser., vol. 12, pp. 225–304. Computer Sci. Press, Rockville (1988)
Grillet, R.A.: Commutative Semigroups. Springer, Berlin (2006)
Grossman, R., Larson, R.G.: Hopf-algebraic structures of families of trees. J. Algebra 26, 184–210 (1989)
Guo, L.: Baxter algebras and the umbral calculus. Adv. Appl. Math. 27, 405–426 (2001)
Guo, L.: Baxter algebras, Stirling numbers and partitions. J. Algebra Appl. 4, 153–164 (2005)
Guo, L., Keigher, W.: Baxter algebras and shuffle products. Adv. Math. 150, 117–149 (2000)
Guo, L., Keigher, W.: On free Baxter algebras: completions and the internal construction. Adv. Math. 151, 101–127 (2000)
Guo, L., Keigher, W.: On differential Rota-Baxter algebras. J. Pure Appl. Algebra (to appear). arXiv: math.RA/0703780
Guo, L., Yu Sit, W.: Enumenation of Rota-Baxter words. In: Proceedings ISSAC 2006, Genoa, Italy, pp. 124–131. ACM Press, New York (2006)
Guo, L., Zhang, B.: Renormalization of multiple zeta values. J. Algebra (to appear). arXiv:math.NT/0606076
Guo, L., Zhang, B.: Differential Birkhoff decomposition and renormalization of multiple zeta values. J. Number Theory (to appear)
Hofmann, K.H., Lawson, J.D., Vinberg, E.B.: Semigroups in Algebra, Geometry and Analysis. de Gruyter, Berlin (1995)
Kolchin, E.: Differential Algebra and Algebraic Groups. Academic Press, New York (1973)
Loday, J.-L., Ronco, M.: Trialgebras and families of polytopes. In: Homotopy Theory: Relations with Algebraic Geometry, Group Cohomology, and Algebraic K-theory. Contemporary Mathematics, vol. 346, pp. 369–398 (2004)
MacLane, S.: Categories for the Working Mathematician. Springer, New York (1971)
Rota, G.: Baxter algebras and combinatorial identities I. Bull. Am. Math. Soc. 5, 325–329 (1969)
Rota, G.: Baxter operators, an introduction. In: Kung, J.P.S. (ed.) Gian-Carlo Rota on Combinatorics, Introductory Papers and Commentaries, pp. 504–512. Birkhäuser, Boston (1995)
Sapounakis, A., Tsikouras, P.: On k-colored Motzkin words, J. Integer Seq. 7 (2004), Article 04.2.5
Shum, K.P., Guo, Y., Ito, M., Fong, Y. (eds.): Semigroups, the International Conference on Semigroups and its Related Topics. Springer, Berlin (1998)
Singer, M. (eds.): Talk at the Second International Workshop on Differential Algebra and Related Topics, Rutgers University, Newark, 12–13 April 2007
Singer, M., van der Put, M.: Galois Theory of Linear Differential Equations. Springer, Berlin (2003)
Stanley, R.R.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999)
Weisstein, E.W., Tree. From MathWorld. http://mathworld.wolfram.com/Tree.html
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Guo, L. Operated semigroups, Motzkin paths and rooted trees. J Algebr Comb 29, 35–62 (2009). https://doi.org/10.1007/s10801-007-0119-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10801-007-0119-7