Pattern Avoidance in Labelled Trees
Séminaire lotharingien de combinatoire, Tome 67 (2012-2015)
Citer cet article
Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website
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.