BinaryTrees

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 14 articles , 1 standard article )

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

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