Journal of Integer Sequences, Vol. 15 (2012), Article 12.1.5

Pattern Avoidance in Ternary Trees


Nathan Gabriel
Department of Mathematics
Rice University
Houston, TX 77251
USA

Katherine Peske
Department of Mathematics and Computer Science
Concordia College
Moorhead, MN 56562
USA

Lara Pudwell
Department of Mathematics and Computer Science
Valparaiso University
Valparaiso, IN 46383
USA

Samuel Tay
Department of Mathematics
Kenyon College
Gambier, OH 43022
USA

Abstract:

This paper considers the enumeration of ternary trees (i.e., rooted ordered trees in which each vertex has 0 or 3 children) avoiding a contiguous ternary tree pattern. We begin by finding recurrence relations for several simple tree patterns; then, for more complex trees, we compute generating functions by extending a known algorithm for pattern-avoiding binary trees. Next, we present an alternate one-dimensional notation for trees which we use to find bijections that explain why certain pairs of tree patterns yield the same avoidance generating function. Finally, we compare our bijections to known "replacement rules" for binary trees and generalize these bijections to a larger class of trees.


Full version:  pdf,    dvi,    ps,    latex,     Maple package    


(Concerned with sequences A000108 A001003 A001764 A006605 A107264 A186241.)


Received November 21 2011; revised version received December 12 2011. Published in Journal of Integer Sequences, December 27 2011.


Return to Journal of Integer Sequences home page