Non-contiguous pattern avoidance in binary trees
From MaRDI portal
Publication:456347
zbMATH Open1252.05086arXiv1203.0795MaRDI QIDQ456347FDOQ456347
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)
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.
Full work available at URL: https://arxiv.org/abs/1203.0795
File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)
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
- Dyck paths, binary words, and Grassmannian permutations avoiding an increasing pattern
- On the sub-permutations of pattern avoiding permutations
- 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
Uses Software
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)
