Pattern avoidance in ternary trees

MaRDI QIDQ5404196zbMATH OpenFDO

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

Publication date 24 March 2014

Full work available at URL https://arxiv.org/abs/1110.2225, http://www.emis.de/journals/JIS/VOL15/Pudwell/pudwell.html

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

zbMATH Keywords

pattern avoidanceternary trees

Mathematics Subject Classification ID

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

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

• 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

Cited in

(20)

• Rooted forests that avoid sets of permutations
• Enumeration of some classes of pattern avoiding matchings, with a glimpse into the matching pattern poset
• Classical and consecutive pattern avoidance in rooted forests
• Supertrees
• Tree series and pattern avoidance in syntax trees
• On generating series of finitely presented operads
• Patterns in treeshelves
• Noncontiguous pattern containment in binary trees
• Pattern avoidance in k-ary heaps
• String pattern avoidance in generalized non-crossing trees
• Non-contiguous pattern avoidance in binary trees
• The rotation -lattice of ternary trees
• Consecutive pattern avoidances in non-crossing trees
• Five classes of pattern avoiding inversion sequences under one roof: generating trees
• Pattern avoidance in labelled trees
• Combinatorial generation via permutation languages. VI: Binary trees
• Recognition and enumeration of the quasi-full rooted trees
• Lattice paths enumerations weighted by ascent lengths
• Pattern-avoiding binary trees -- generation, counting, and bijections
• Pattern avoidance in binary trees

Describes a project that uses

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)