اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدWilf classification of triples of 4-letter patterns
137
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 reduces 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.
قيم البحث
اقرأ أيضاً
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.
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 exte
nsions 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.
An empty simplex is a lattice simplex with only its vertices as lattice points. Their classification in dimension three was completed by White in 1964. In dimension four, the same task was started in 1988 by Mori, Morrison, and Morrison, with their m
otivation coming from the close relationship between empty simplices and terminal quotient singularities. They conjectured a classification of empty simplices of prime volume, modulo finitely many exceptions. Their conjecture was proved by Sankaran (1990) with a simplified proof by Bober (2009). The same classification was claimed by Barile et al. in 2011 for simplices of non-prime volume, but this statement was proved wrong by Blanco et al. (2016+). In this article we complete the classification of $4$-dimensional empty simplices. In doing so we correct and complete the classification claimed by Barile et al., and we also compute all the finitely many exceptions, by first proving an upper bound for their volume. The whole classification has: - One $3$-parameter family, consisting of simplices of width equal to one. - Two $2$-parameter families (the one in Mori et al., plus a second new one). - Forty-six $1$-parameter families (the 29 in Mori et al., plus 17 new ones). - $2461$ individual simplices not belonging to the above families, with volumes ranging between 29 and 419. We characterize the infinite families of empty simplices in terms of lower dimensional point configurations that they project to, with techniques that can be applied to higher dimensions and larger classes of lattice polytopes.
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.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
