Tree series and pattern avoidance in syntax trees

DOI10.1016/J.JCTA.2020.105285MaRDI QIDQ2194759zbMATH OpenOpenAlexFDO

Authors Samuele Giraudo

Publication date 7 September 2020

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.00677

zbMATH Keywords

enumerationformal power seriesoperadpattern avoidance

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Enumeration in graph theory (05C30) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Operads (general) (18M60)

Abstract: A syntax tree is a planar rooted tree where internal nodes are labeled on a graded set of generators. There is a natural notion of occurrence of contiguous pattern in such trees. We describe a way, given a set of generators $mathfrakG$ and a set of patterns $mathcalP$, to enumerate the trees constructed on $mathfrakG$ and avoiding $mathcalP$. The method is built around inclusion-exclusion formulas forming a system of equations on formal power series of trees, and composition operations of trees. This does not require particular conditions on the set of patterns to avoid. We connect this result to the theory of nonsymmetric operads. Syntax trees are the elements of such free structures, so that any operad can be seen as a quotient of a free operad. Moreover, in some cases, the elements of an operad can be seen as trees avoiding some patterns. Relying on this, we use operads as devices for enumeration: given a set of combinatorial objects we want enumerate, we endow it with the structure of an operad, understand it in term of trees and pattern avoidance, and use our method to count them. Several examples are provided.

Recommendations

• Pattern avoidance in labelled trees
• Pattern avoidance in binary trees
• Pattern avoidance in ternary trees
• Non-contiguous pattern avoidance in binary trees
• Patterns in trees

Cites work

• A Poincaré-Birkhoff-Witt criterion for Koszul operads
• Algebraic operads
• An Inversion Theorem for Cluster Decompositions of Sequences with Distinguished Subsequences
• Cofree Hopf algebras.
• Colored operads, series on colored operads, and combinatorial generating systems
• Combinatorial operads from monoids
• Generalized bialgebras and triples of operads
• Gröbner bases for operads
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3108822 (Why is no real title available?)
• Inversion of integral series enumerating planar trees
• Koszul duality for operads
• L-algebras, triplicial-algebras, within an equivalence of categories motivated by graphs
• Nonsymmetric operads in combinatorics
• On generating series of finitely presented operads
• On the structure of cofree Hopf algebras
• Operads and algebraic combinatorics of trees
• Pattern avoidance in binary trees
• Pattern avoidance in ternary trees
• Set Operads in Combinatorics and Computer Science
• Supertrees
• The Anticyclic Operad of Moulds
• The Goulden—Jackson cluster method: extensions, applications and implementations
• Trees and jumps and real roots.

Cited in

(5)

• The combinator M and the Mockingbird lattice
• Mockingbird lattices
• Combinatorial generation via permutation languages. VI: Binary trees
• Pattern-avoiding binary trees -- generation, counting, and bijections
• Clones of pigmented words and realizations of special classes of monoids

Describes a project that uses

Uses Software

• GJseries
• DAVID_IAN
• NAIVE
• GJsqfree
• operads
• BinaryTrees
• OEIS
• GJSAW
• JODO
• BLANKS
• SYMGJ
• SPGJ

This page was built for publication: Tree series and pattern avoidance in syntax trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2194759)