Non-contiguous pattern avoidance in binary trees
type: Item
instance of: scholarly article
title: Non-contiguous pattern avoidance in binary trees
zbMATH Open document ID: 1252.05086
author: Michael Dairyko
author: Samantha Tyner
author: Casey Wynn
author: Lara Pudwell
published in: The Electronic Journal of Combinatorics
publication date: 2012-10-24T00:00:00Z
full work available at URL: https://arxiv.org/abs/1203.0795
full work available at URL: v19i3p22
review text: Summary: 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 and show that there is exactly one Wilf class of \(k\)-leaf tree patterns for any positive integer \(k\). In addition, we give a bijection between between certain sets of pattern-avoiding trees and sets of pattern-avoiding permutations. Finally, we enumerate binary trees that simultaneously avoid more than one tree pattern.
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 6098364
zbMATH Keywords: binary tree
zbMATH Keywords: pattern avoidance
describes a project that uses: OEIS
describes a project that uses: BinaryTrees
MaRDI profile type: Publication
arXiv ID: 1203.0795
Recommended article: Noncontiguous pattern containment in binary trees
Recommended article: Pattern avoidance in binary trees
Recommended article: Consecutive pattern avoidances in non-crossing trees
Recommended article: Pattern Avoidance in Ternary Trees
Recommended article: Pattern avoidance in labelled trees
Recommended article: Pattern Avoidance in Generalized Non-crossing Trees
Recommended article: Q4361713
Recommended article: Nonlinear pattern matching in trees
Recommended article: Q3795241
description: scientific article; zbMATH DE number 6098364