Non-contiguous pattern avoidance in binary trees

MaRDI QIDQ456347zbMATH OpenFDO

Authors Michael Dairyko, Samantha Tyner, Casey Wynn, Lara Pudwell

Publication date 24 October 2012

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.0795, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p22

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 avoidancebinary tree

Mathematics Subject Classification ID

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

Abstract: In this paper we consider the enumeration of binary trees avoiding non-contiguous binary tree patterns. We begin by computing closed formulas for the number of trees avoiding a single binary tree pattern with 4 or fewer leaves and compare these results to analogous work for contiguous tree patterns. Next, we give an explicit generating function that counts binary trees avoiding a single non-contiguous tree pattern according to number of leaves. In addition, we enumerate binary trees that simultaneously avoid more than one tree pattern. Finally, we explore connections between pattern-avoiding trees and pattern-avoiding permutations.

Recommendations

• Noncontiguous pattern containment in binary trees
• Pattern avoidance in binary trees
• Consecutive pattern avoidances in non-crossing trees
• Pattern avoidance in ternary trees
• Pattern avoidance in labelled trees
• String pattern avoidance in generalized non-crossing trees
• scientific article; zbMATH DE number 1080355
• Nonlinear pattern matching in trees
• scientific article; zbMATH DE number 4060735

Cited in

(18)

• The Dyck pattern poset
• Classical and consecutive pattern avoidance in rooted forests
• Consecutive pattern avoidances in non-crossing trees
• Pattern avoidance in \(k\)-ary heaps
• Pattern avoidance in labelled trees
• Combinatorial generation via permutation languages. VI: Binary trees
• On the sub-permutations of pattern avoiding permutations
• Dyck paths, binary words, and Grassmannian permutations avoiding an increasing pattern
• A general theory of Wilf-equivalence for Catalan structures
• Supertrees
• Pattern avoidance in binary trees
• String pattern avoidance in generalized non-crossing trees
• Pattern avoidance in ternary trees
• Tree series and pattern avoidance in syntax trees
• Counting embeddings of rooted trees into families of rooted trees
• Permutation classes and polyomino classes with excluded submatrices
• 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

• BinaryTrees
• OEIS

This page was built for publication: Non-contiguous pattern avoidance in binary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456347)