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