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.
Recommendations
Cited in
(17)- Non-contiguous pattern avoidance in binary trees
- Classical and consecutive pattern avoidance in rooted forests
- On generating series of finitely presented operads
- Consecutive pattern avoidances in non-crossing trees
- Pattern avoidance in \(k\)-ary heaps
- Pattern avoidance in labelled trees
- The rotation \(\chi\)-lattice of ternary trees
- Combinatorial generation via permutation languages. VI: Binary trees
- Five classes of pattern avoiding inversion sequences under one roof: generating trees
- Patterns in treeshelves
- Supertrees
- Pattern avoidance in binary trees
- String pattern avoidance in generalized non-crossing trees
- Rooted forests that avoid sets of permutations
- Tree series and pattern avoidance in syntax trees
- Noncontiguous pattern containment in binary trees
- Enumeration of some classes of pattern avoiding matchings, with a glimpse into the matching pattern poset
Describes a project that uses
Uses Software
This page was built for publication: Pattern avoidance in ternary trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404196)
