اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدWilf Equivalences and Stanley-Wilf Limits for Patterns in Rooted Labeled Forests
140
0
0.0
(
0
)
تأليف
Michael Ren
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Building off recent work of Garg and Peng, we continue the investigation into classical and consecutive pattern avoidance in rooted forests, resolving some of their conjectures and questions and proving generalizations whenever possible. Through extensions of the forest Simion-Schmidt bijection introduced by Anders and Archer, we demonstrate a new family of forest-Wilf equivalences, completing the classification of forest-Wilf equivalence classes for sets consisting of a pattern of length 3 and a pattern of length at most $5$. We also find a new family of nontrivial c-forest-Wilf equivalences between single patterns using the forest analogue of the Goulden-Jackson cluster method, showing that a $(1-o(1))^n$-fraction of patterns of length $n$ satisfy a nontrivial c-forest-Wilf equivalence and that there are c-forest-Wilf equivalence classes of patterns of length $n$ of exponential size. Additionally, we consider a forest analogue of super-strong-c-Wilf equivalence, introduced for permutations by Dwyer and Elizalde, showing that super-strong-c-forest-Wilf equivalences are trivial by enumerating linear extensions of forest cluster posets. Finally, we prove a forest analogue of the Stanley-Wilf conjecture for avoiding a single pattern as well as certain other sets of patterns. Our techniques are analytic, easily generalizing to different types of pattern avoidance and allowing for computations of convergent lower bounds of the forest Stanley-Wilf limit in the cases covered by our result. We end with several open questions and directions for future research, including some on the limit distributions of certain statistics of pattern-avoiding forests.
قيم البحث
اقرأ أيضاً
We launch a systematic study of the refined Wilf-equivalences by the statistics $mathsf{comp}$ and $mathsf{iar}$, where $mathsf{comp}(pi)$ and $mathsf{iar}(pi)$ are the number of components and the length of the initial ascending run of a permutation
$pi$, respectively. As Comtet was the first one to consider the statistic $mathsf{comp}$ in his book {em Analyse combinatoire}, any statistic equidistributed with $mathsf{comp}$ over a class of permutations is called by us a {em Comtet statistic} over such class. This work is motivated by a triple equidistribution result of Rubey on $321$-avoiding permutations, and a recent result of the first and third authors that $mathsf{iar}$ is a Comtet statistic over separable permutations. Some highlights of our results are: (1) Bijective proofs of the symmetry of the double Comtet distribution $(mathsf{comp},mathsf{iar})$ over several Catalan and Schroder classes, preserving the values of the left-to-right maxima. (2) A complete classification of $mathsf{comp}$- and $mathsf{iar}$-Wilf-equivalences for length $3$ patterns and pairs of length $3$ patterns. Calculations of the $(mathsf{des},mathsf{iar},mathsf{comp})$ generating functions over these pattern avoiding classes and separable permutations. (3) A further refinement by the Comtet statistic $mathsf{iar}$, of Wangs recent descent-double descent-Wilf equivalence between separable permutations and $(2413,4213)$-avoiding permutations.
We determine all 242 Wilf classes of triples of 4-letter patterns by showing that there are 32 non-singleton Wilf classes. There are 317 symmetry classes of triples of 4-letter patterns and after computer calculation of initial terms, the problem red
uces to showing that counting sequences that appear to be the same (agree in the first 16 terms) are in fact identical. The insertion encoding algorithm (INSENC) accounts for many of these and some others have been previously counted; in this paper, we find the generating function for each of the remaining 36 triples and it turns out to be algebraic in every case. Our methods are both combinatorial and analytic, including decompositions by left-right maxima and by initial letters. Sometimes this leads to an algebraic equation for the generating function, sometimes to a functional equation or a multi-index recurrence that succumbs to the kernel method. A particularly nice so-called cell decomposition is used in one case and a bijection is used for another.
Stankova and West showed that for any non-negative integer $s$ and any permutation $gamma$ of ${4,5,dots,s+3}$ there are as many permutations that avoid $231gamma$ as there are that avoid $312gamma$. We extend this result to the setting of words.
Recently, it has been determined that there are 242 Wilf classes of triples of 4-letter permutation patterns by showing that there are 32 non-singleton Wilf classes. Moreover, the generating function for each triple lying in a non-singleton Wilf clas
s has been explicitly determined. In this paper, toward the goal of enumerating avoiders for the singleton Wilf classes, we obtain the generating function for all but one of the triples containing 1324. (The exceptional triple is conjectured to be intractable.) Our methods are both combinatorial and analytic, including generating trees, recurrence relations, and decompositions by left-right maxima. Sometimes this leads to an algebraic equation for the generating function, sometimes to a functional equation or a multi-index recurrence amenable to the kernel method.
Let $pi in mathfrak{S}_m$ and $sigma in mathfrak{S}_n$ be permutations. An occurrence of $pi$ in $sigma$ as a consecutive pattern is a subsequence $sigma_i sigma_{i+1} cdots sigma_{i+m-1}$ of $sigma$ with the same order relations as $pi$. We say that
patterns $pi, tau in mathfrak{S}_m$ are strongly c-Wilf equivalent if for all $n$ and $k$, the number of permutations in $mathfrak{S}_n$ with exactly $k$ occurrences of $pi$ as a consecutive pattern is the same as for $tau$. In 2018, Dwyer and Elizalde conjectured (generalizing a conjecture of Elizalde from 2012) that if $pi, tau in mathfrak{S}_m$ are strongly c-Wilf equivalent, then $(tau_1, tau_m)$ is equal to one of $(pi_1, pi_m)$, $(pi_m, pi_1)$, $(m+1 - pi_1, m+1-pi_m)$, or $(m+1 - pi_m, m+1 - pi_1)$. We prove this conjecture using the cluster method introduced by Goulden and Jackson in 1979, which Dwyer and Elizalde previously applied to prove that $|pi_1 - pi_m| = |tau_1 - tau_m|$. A consequence of our result is the full classification of c-Wilf equivalence for a special class of permutations, the non-overlapping permutations. Our approach uses analytic methods to approximate the number of linear extensions of the cluster posets of Elizalde and Noy.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
