Classical length-5 pattern-avoiding permutations
From MaRDI portal
Abstract: We have made a systematic numerical study of the 16 Wilf classes of length-5 classical pattern-avoiding permutations from their generating function coefficients. We have extended the number of known coefficients in fourteen of the sixteen classes. Careful analysis, including sequence extension, has allowed us to estimate the growth constant of all classes, and in some cases to estimate the sub-dominant power-law term associated with the exponential growth. In six of the sixteen classes we find the familiar power-law behaviour, so that the coefficients behave like while in the remaining ten cases we find a stretched exponential as the most likely sub-dominant term, so that the coefficients behave like where We have also classified the 120 possible permutations into the 16 distinct classes. We give compelling numerical evidence, and in one case a proof, that all 16 Wilf-class generating function coefficients can be represented as moments of a non-negative measure on Such sequences are known as {em Stieltjes moment sequences}. They have a number of nice properties, such as log-convexity, which can be used to provide quite strong rigorous lower bounds. Stronger bounds still can be established under plausible monotonicity assumptions about the terms in the continued-fraction expansion of the generating functions implied by the Stieltjes property. In this way we provide strong (non-rigorous) lower bounds to the growth constants, which are sometimes within a few percent of the exact value.
Recommendations
- Enumeration and Wilf-classification of permutations avoiding five patterns of length 4
- On consecutive pattern-avoiding permutations of length 4, 5 and beyond
- Some equinumerous pattern-avoiding classes of permutations
- Pattern avoidance classes and subpermutations
- Pattern avoiding meandric permutations
- On pattern avoiding alternating permutations
- Classical sequences revisited with permutations avoiding dotted pattern
- On partially ordered patterns of length 4 and 5 in permutations
- Pattern avoidance in partial permutations
- Enumerating pattern avoidance for affine permutations
Cites work
- scientific article; zbMATH DE number 3026637 (Why is no real title available?)
- 1324-avoiding permutations revisited
- A computational approach to the Thompson group F
- A generalization of Simion-Schmidt's bijection for restricted permutations
- A new class of Wilf-equivalent permutations
- A variational formula for the free energy of the partially directed polymer collapse
- An Efficient Method for Indexing All Topological Orders of a Directed Graph
- Analysis of series expansions for non-algebraic singularities
- Asymptotic values for degrees associated with strips of Young diagrams
- Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
- Graph-Based Algorithms for Boolean Function Manipulation
- Large deviations and ratio limit theorems for pattern-avoiding permutations
- New records in Stanley-Wilf limits
- On the growth of merges and staircases of permutation classes
- Permutation classes
- Series extension: predicting approximate series coefficients from a finite number of exact coefficients
- Stieltjes moment sequences for pattern-avoiding permutations
- Symmetric functions and P-recursiveness
- The connective constant of the honeycomb lattice equals \(\sqrt{2+\sqrt 2}\)
- The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns
- The permutations \(123p_4\dots p_m\) and \(321p_4\dots p_m\) are Wilf-equivalent
- Wilf-equivalence for singleton classes
- Words in linear groups, random walks, automata and P-recursiveness
- \(\pi \)DD: a new decision diagram for efficient problem solving in permutation space
Cited in
(3)
This page was built for publication: Classical length-5 pattern-avoiding permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2161199)
