Séminaire Lotharingien de Combinatoire, B67b (2012), 27 pp.
Vladimir Dotsenko
Pattern Avoidance in Labelled Trees
Abstract.
We discuss a new notion of pattern avoidance motivated by 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 exact and
asymptotic enumeration.
Received: October 20, 2011.
Revised: December 12, 2011.
Accepted: December 31, 2011.
Final Version: January 2, 2012.
The following versions are available: