Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEnumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns
122
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 class 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.
rate research
Read More
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.
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 present the first combinatorial scheme for counting labelled 4-regular planar graphs through a complete recursive decomposition. More precisely, we show that the exponential generating function of labelled 4-regular planar graphs can be computed effectively as the solution of a system of equations, from which the coefficients can be extracted. As a byproduct, we also enumerate labelled 3-connected 4-regular planar graphs, and simple 4-regular rooted maps.
Building on previous work by the present authors [Proc. London Math. Soc. 119(2):358--378, 2019], we obtain a precise asymptotic estimate for the number $g_n$ of labelled 4-regular planar graphs. Our estimate is of the form $g_n sim gcdot n^{-7/2} rho^{-n} n!$, where $g>0$ is a constant and $rho approx 0.24377$ is the radius of convergence of the generating function $sum_{nge 0}g_n x^n/n!$, and conforms to the universal pattern obtained previously in the enumeration of planar graphs. In addition to analytic methods, our solution needs intensive use of computer algebra in order to work with large systems of polynomials equations. In particular, we use evaluation and Lagrange interpolation in order to compute resultants of multivariate polynomials. We also obtain asymptotic estimates for the number of 2- and 3-connected 4-regular planar graphs, and for the number of 4-regular simple maps, both connected and 2-connected.
We show that permutations of size $n$ avoiding both of the dashed patterns 32-41 and 41-32 are equinumerous with indecomposable set partitions of size $n+1$, and deduce a related result.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
