Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn (shape-)Wilf-equivalence for words
103
0
0.0
(
0
)
Authors
Ting Guo
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
A universal word for a finite alphabet $A$ and some integer $ngeq 1$ is a word over $A$ such that every word in $A^n$ appears exactly once as a subword (cyclically or linearly). It is well-known and easy to prove that universal words exist for any $A$ and $n$. In this work we initiate the systematic study of universal partial words. These are words that in addition to the letters from $A$ may contain an arbitrary number of occurrences of a special `joker symbol $Diamond otin A$, which can be substituted by any symbol from $A$. For example, $u=0Diamond 011100$ is a linear partial word for the binary alphabet $A={0,1}$ and for $n=3$ (e.g., the first three letters of $u$ yield the subwords $000$ and $010$). We present results on the existence and non-existence of linear and cyclic universal partial words in different situations (depending on the number of $Diamond$s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer.
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 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
