Pattern avoidance in binary trees

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:117

Article

Rowland, Eric S.

关键词: Pattern avoidance;    Binary trees;    Wilf equivalence;    Algebraic generating functions;    Dyck words;   

DOI  :  10.1016/j.jcta.2010.03.004

来源: Elsevier

【 摘 要 】

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. (C) 2010 Elsevier Inc. All rights reserved.

【 授权许可】

Free