Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNon-Contiguous Pattern Avoidance in Binary Trees
182
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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.
rate research
Read More
In this paper, the problem of pattern avoidance in generalized non-crossing trees is studied. The generating functions for generalized non-crossing trees avoiding patterns of length one and two are obtained. Lagrange inversion formula is used to obtain the explicit formulas for some special cases. Bijection is also established between generalized non-crossing trees with special pattern avoidance and the little Schr{o}der paths.
Given a set of permutations Pi, let S_n(Pi) denote the set of permutations in the symmetric group S_n that avoid every element of Pi in the sense of pattern avoidance. Given a subset S of {1,...,n-1}, let F_S be the fundamental quasisymmetric function indexed by S. Our object of study is the generating function Q_n(Pi) = sum F_{Des sigma} where the sum is over all sigma in S_n(Pi) and Des sigma is the descent set of sigma. We characterize those Pi contained in S_3 such that Q_n(Pi) is symmetric or Schur nonnegative for all n. In the process, we show how each of the resulting Pi can be obtained from a theorem or conjecture involving more general sets of patterns. In particular, we prove results concerning symmetries, shuffles, and Knuth classes, as well as pointing out a relationship with the arc permutations of Elizalde and Roichman. Various conjectures and questions are mentioned throughout.
Jelinek, Mansour, and Shattuck studied Wilf-equivalence among pairs of patterns of the form ${sigma,tau}$ where $sigma$ is a set partition of size $3$ with at least two blocks. They obtained an upper bound for the number of Wilf-equivalence classes for such pairs. We show that their upper bound is the exact number of equivalence classes, thus solving a problem posed by them.
The study of pattern containment and avoidance for linear permutations is a well-established area of enumerative combinatorics. A cyclic permutation is the set of all rotations of a linear permutation. Callan initiated the study of permutation avoidance in cyclic permutations and characterized the avoidance classes for all single permutations of length 4. We continue this work. In particular, we establish a cyclic variant of the Erdos-Szekeres Theorem that any linear permutation of length mn+1 must contain either the increasing pattern of length m+1 or the decreasing pattern of length n+1. We then derive results about avoidance of multiple patterns of length 4. We also determine generating functions for the cyclic descent statistic on these classes. Finally, we end with various open questions and avenues for future research.
Let S_n be the nth symmetric group. Given a set of permutations Pi we denote by S_n(Pi) the set of permutations in S_n which avoid Pi in the sense of pattern avoidance. Consider the generating function Q_n(Pi) = sum_pi F_{Des pi} where the sum is over all pi in S_n(Pi) and F_{Des pi} is the fundamental quasisymmetric function corresponding to the descent set of pi. Hamaker, Pawlowski, and Sagan introduced Q_n(Pi) and studied its properties, in particular, finding criteria for when this quasisymmetric function is symmetric or even Schur nonnegative for all n >= 0. The purpose of this paper is to continue their investigation answering some of their questions, proving one of their conjectures, as well as considering other natural questions about Q_n(Pi). In particular we look at Pi of small cardinality, superstandard hooks, partial shuffles, Knuth classes, and a stability property.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
