##
**
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**