Pattern avoidance in ternary trees

zbMATH Open1292.05139arXiv1110.2225MaRDI QIDQ5404196FDOQ5404196

Authors: Nathan Gabriel, Katherine Peske, Samuel Tay, Lara Pudwell 

Publication date: 24 March 2014

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 work available at URL: https://arxiv.org/abs/1110.2225

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Pattern avoidance in binary trees
• Non-contiguous pattern avoidance in binary trees
• Pattern avoidance in labelled trees
• Patterns in trees
• Consecutive pattern avoidances in non-crossing trees

zbMATH Keywords

pattern avoidanceternary trees

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30)

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

Uses Software

• OEIS
• BinaryTrees
• NAIVE
• DAVID_IAN
• JODO
• BLANKS
• SYMGJ
• SPGJ
• GJseries
• GJSAW
• GJsqfree

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)