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: