Pattern avoidance in binary trees

Abstract

This paper considers the enumeration of trees avoiding a contiguous pattern. We provide an algorithm for computing the generating function that counts n-leaf binary trees avoiding a given binary tree pattern t. Equipped with this counting mechanism, we study the analogue of Wilf equivalence in which two tree patterns are equivalent if the respective n-leaf trees that avoid them are equinumerous. We investigate the equivalence classes combinatorially. Toward establishing bijective proofs of tree pattern equivalence, we develop a general method of restructuring trees that conjecturally succeeds to produce an explicit bijection for each pair of equivalent tree patterns.

19 pages, many images; published version

Cited by in corpus (16)

• On generating series of finitely presented operads
• Tree series and pattern avoidance in syntax trees
• On Stochastic Rewriting and Combinatorics via Rule-Algebraic Methods
• Pattern avoidance in forests of binary shrubs
• Permutation classes and polyomino classes with excluded submatrices
• Classical and consecutive pattern avoidance in rooted forests
• Unbalanced subtrees in binary rooted ordered and un-ordered trees
• Quotients of the magmatic operad: lattice structures and convergent rewrite systems
• The Dyck pattern poset
• Non-Contiguous Pattern Avoidance in Binary Trees
• Pattern Avoidance in Task-Precedence Posets
• Modular Catalan Numbers
• Proofs of Conjectures about Pattern-Avoiding Linear Extensions
• On the sub-permutations of pattern avoiding permutations
• Wilf classes of non-symmetric operads
• Pattern Avoidance in Ternary Trees