Pattern avoidance in binary trees. 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.

References in zbMATH (referenced in 16 articles , 1 standard article )

Showing results 1 to 16 of 16.
Sorted by year (citations)

  1. Hein, Nickolas; Huang, Jia: Modular Catalan numbers (2017)
  2. Frosini, Andrea; Guerrini, Veronica; Rinaldi, Simone: Geometric properties of matrices induced by pattern avoidance (2016)
  3. Levin, Derek; Pudwell, Lara K.; Riehl, Manda; Sandberg, Andrew: Pattern avoidance in $k$-ary heaps (2016)
  4. Zubkov, Andrey M.; Kruglov, Vasiliy I.: On coincidences of tuples in a binary tree with random labels of vertices (2016)
  5. Khoroshkin, Anton; Piontkovski, Dmitri: On generating series of finitely presented operads (2015)
  6. Rowland, Eric; Yassawi, Reem: Automatic congruences for diagonals of rational functions (2015)
  7. Bacher, Axel; Bernini, Antonio; Ferrari, Luca; Gunby, Benjamin; Pinzani, Renzo; West, Julian: The Dyck pattern poset (2014)
  8. Disanto, Filippo; Wiehe, Thomas: On the sub-permutations of pattern avoiding permutations (2014)
  9. Pudwell, Lara; Scholten, Connor; Schrock, Tyler; Serrato, Alexa: Noncontiguous pattern containment in binary trees (2014)
  10. Bernini, Antonia; Ferrari, Luca; Pinzani, Renzo; West, Julian: Pattern-avoiding Dyck paths (2013)
  11. Disanto, Filippo: Unbalanced subtrees in binary rooted ordered and un-ordered trees (2013)
  12. Cooper, Bobbe; Rowland, Eric; Zeilberger, Doron: Toward a language theoretic proof of the four color theorem (2012)
  13. Dairyko, Michael; Pudwell, Lara; Tyner, Samantha; Wynn, Casey: Non-contiguous pattern avoidance in binary trees (2012)
  14. Dotsenko, Vladimir: Pattern avoidance in labelled trees (2012)
  15. Gabriel, Nathan; Peske, Katherine; Pudwell, Lara; Tay, Samuel: Pattern avoidance in ternary trees (2012)
  16. Rowland, Eric S.: Pattern avoidance in binary trees (2010)