Pattern avoidance in binary trees
From MaRDI portal
Abstract: This paper considers the enumeration of trees avoiding a contiguous pattern. We provide an algorithm for computing the generating function that counts n-leaf binary trees avoiding a given binary tree pattern t. Equipped with this counting mechanism, we study the analogue of Wilf equivalence in which two tree patterns are equivalent if the respective n-leaf trees that avoid them are equinumerous. We investigate the equivalence classes combinatorially. Toward establishing bijective proofs of tree pattern equivalence, we develop a general method of restructuring trees that conjecturally succeeds to produce an explicit bijection for each pair of equivalent tree patterns.
Recommendations
- Non-contiguous pattern avoidance in binary trees
- Pattern avoidance in ternary trees
- Pattern avoidance in labelled trees
- Consecutive pattern avoidances in non-crossing trees
- Noncontiguous pattern containment in binary trees
- scientific article; zbMATH DE number 1080355
- String pattern avoidance in generalized non-crossing trees
- Patterns with bounded treewidth
- Patterns with Bounded Treewidth
Cites work
- scientific article; zbMATH DE number 177816 (Why is no real title available?)
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- An Inversion Theorem for Cluster Decompositions of Sequences with Distinguished Subsequences
- Analytic combinatorics
- Counting strings in Dyck paths
- Dyck path enumeration
- Motzkin numbers
- Patterns and pattern-matching in trees: An analysis
- The Goulden—Jackson cluster method: extensions, applications and implementations
- The On-Line Encyclopedia of Integer Sequences
- \textsc{IntegerSequences}: a package for computing with \(k\)-regular sequences
Cited in
(36)- The Dyck pattern poset
- Non-contiguous pattern avoidance in binary trees
- Patterns with Bounded Treewidth
- Pattern-avoiding binary trees -- generation, counting, and bijections
- Automatic congruences for diagonals of rational functions
- Geometric properties of matrices induced by pattern avoidance
- Classical and consecutive pattern avoidance in rooted forests
- On generating series of finitely presented operads
- Consecutive patterns in Catalan words and the descent distribution
- Stanley-Wilf limits for patterns in rooted labeled forests
- Consecutive pattern avoidances in non-crossing trees
- Pattern avoidance in forests of binary shrubs
- A 2D non-overlapping code over a q-ary alphabet
- Pattern avoidance in k-ary heaps
- Pattern avoidance in labelled trees
- Two-dimensional q-ary non-overlapping codes
- Modular Catalan numbers
- Quotients of the magmatic operad: lattice structures and convergent rewrite systems
- On coincidences of tuples in a binary tree with random labels of vertices
- Combinatorial generation via permutation languages. VI: Binary trees
- On the sub-permutations of pattern avoiding permutations
- BinaryTrees
- Dyck paths, binary words, and Grassmannian permutations avoiding an increasing pattern
- Patterns in treeshelves
- On coincidences of tuples in a \(q\)-ary tree with random labels of vertices
- scientific article; zbMATH DE number 7456060 (Why is no real title available?)
- String pattern avoidance in generalized non-crossing trees
- Pattern avoidance in ternary trees
- Restricted generating trees for weak orderings
- Rooted forests that avoid sets of permutations
- 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
- Wilf equivalences for patterns in rooted labeled forests
- Enumeration of some classes of pattern avoiding matchings, with a glimpse into the matching pattern poset
This page was built for publication: Pattern avoidance in binary trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q986111)
