Pattern Avoidance in Ternary Trees

Details Pattern Avoidance in Ternary Trees Pattern Avoidance in Ternary Trees

2011-10-10

arxiv.org/abs/1110.2225v2

Journal of Integer Sequences 15 (2012) 12.1.5

Mathematics

Combinatorics

19 pages, 11 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Pattern Avoidance in Ternary Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pattern Avoidance in Ternary Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pattern Avoidance in Ternary Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-471154