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