Pattern avoidance in binary trees Export

@article{citeulike:3187445, abstract = {This paper introduces the notion of pattern avoidance in binary trees. We provide an algorithm for computing the generating function that counts the number of 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 trees that avoid them are equinumerous. We investigate the equivalence classes combinatorially, finding some relationships to Dyck words avoiding a given subword. Toward establishing bijective proofs of tree pattern equivalence, we develop a general method of restructuring trees that (conjecturally) always succeeds to produce an explicit bijection.}, archivePrefix = {arXiv}, author = {Rowland, Eric S.}, citeulike-article-id = {3187445}, citeulike-linkout-0 = {http://arxiv.org/abs/0809.0488}, citeulike-linkout-1 = {http://arxiv.org/pdf/0809.0488}, eprint = {0809.0488}, keywords = {combinatorics, fun, graphs, mathematics}, month = {Sep}, posted-at = {2008-09-03 19:50:46}, priority = {2}, title = {Pattern avoidance in binary trees}, url = {http://arxiv.org/abs/0809.0488}, year = {2008} }

TY - JOUR ID - citeulike:3187445 L3 - citeulike-article-id:3187445 N2 - This paper introduces the notion of pattern avoidance in binary trees. We provide an algorithm for computing the generating function that counts the number of 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 trees that avoid them are equinumerous. We investigate the equivalence classes combinatorially, finding some relationships to Dyck words avoiding a given subword. Toward establishing bijective proofs of tree pattern equivalence, we develop a general method of restructuring trees that (conjecturally) always succeeds to produce an explicit bijection. TI - Pattern avoidance in binary trees KW - combinatorics KW - fun KW - graphs KW - mathematics AU - Rowland, Eric PY - 2008/Sep/02/ UR - http://arxiv.org/abs/0809.0488 ER -