Pattern avoidance in binary trees |
| |
Authors: | Eric S. Rowland |
| |
Affiliation: | Mathematics Department, Tulane University, New Orleans, LA 70118, USA |
| |
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. |
| |
Keywords: | Pattern avoidance Binary trees Wilf equivalence Algebraic generating functions Dyck words |
本文献已被 ScienceDirect 等数据库收录! |
|