Pattern avoidance in labelled trees

Abstract

We discuss a new notion of pattern avoidance motivated by the operad theory: pattern avoidance in planar labelled trees. It is a generalisation of various types of consecutive pattern avoidance studied before: consecutive patterns in words, permutations, coloured permutations etc. The notion of Wilf equivalence for patterns in permutations admits a straightforward generalisation for (sets of) tree patterns; we describe classes for trees with small numbers of leaves, and give several bijections between trees avoiding pattern sets from the same class. We also explain a few general results for tree pattern avoidance, both for the exact and the asymptotic enumeration.

27 pages, corrected various misprints, added an appendix explaining the operadic context

Cited by in corpus (5)

• On generating series of finitely presented operads
• A family of symmetric functions associated with Stirling permutations
• Growth in varieties of multioperator algebras and Groebner bases in operads
• Non-Contiguous Pattern Avoidance in Binary Trees
• Wilf classes of non-symmetric operads