Tree series and pattern avoidance in syntax trees

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 $\mathfrak{G}$ and a set of patterns $\mathcal{P}$, to enumerate the trees constructed on $\mathfrak{G}$ and avoiding $\mathcal{P}$. 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.

31 pages

References in corpus (3)

• Rooted trees and an exponential-like series
• Nonsymmetric operads in combinatorics
• Colored operads, series on colored operads, and combinatorial generating systems

Cited by in corpus (6)

• Nonsymmetric operads in combinatorics
• Generalizations of the associative operad and convergent rewrite systems
• Quotients of the magmatic operad: lattice structures and convergent rewrite systems
• Wilf classes of non-symmetric operads
• Clones of pigmented words and realizations of special classes of monoids
• The combinator $\mathbf{M}$ and the Mockingbird lattice