Refining enumeration schemes to count according to permutation statistics
From MaRDI portal
(Redirected from Publication:405263)
Abstract: We consider the question of computing the distribution of a permutation statistics over restricted permutations via enumeration schemes. The restricted permutations are those avoiding sets of vincular patterns (which include both classical and consecutive patterns), and the statistics are described in the number of copies of certain vincular patterns such as the descent statistic and major index. An enumeration scheme is a polynomial-time algorithm (specifically, a system of recurrence relations) to compute the number of permutations avoiding a given set of vincular patterns. Enumeration schemes' most notable feature is that they may be discovered and proven via only finite computation. We prove that when a finite enumeration scheme exists to compute the number of permutations avoiding a given set of vincular patterns, the scheme can also compute the distribution of certain permutation statistics with very little extra computation.
Recommendations
- Refining enumeration schemes to count according to the inversion number
- Enumeration schemes for vincular patterns
- Enumeration schemes for words avoiding permutations
- Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
- Distributions of statistics over pattern-avoiding permutations
Cites work
- scientific article; zbMATH DE number 5557896 (Why is no real title available?)
- scientific article; zbMATH DE number 2024859 (Why is no real title available?)
- scientific article; zbMATH DE number 2192093 (Why is no real title available?)
- Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations
- Enumeration Schemes for Restricted Permutations
- Enumeration schemes and, more importantly, their automatic generation
- Enumeration schemes for permutations avoiding barred patterns
- Enumeration schemes for vincular patterns
- Enumeration schemes for words avoiding permutations
- Expected patterns in permutation classes
- Finding regular insertion encodings for permutation classes
- Generalized pattern avoidance
- Generalized permutation patterns and a classification of the Mahonian statistics
- Partially ordered generalized patterns
- Permutation patterns and statistics
- Permutations with restricted patterns and Dyck paths
- Refining enumeration schemes to count according to the inversion number
- Restricted 1-3-2 permutations and generalized patterns
- Restricted permutations
- Shape-Wilf-equivalences for vincular patterns
- Some permutations with forbidden subsequences and their inversion number
- Surprising symmetries in objects counted by Catalan numbers
- The absence of a pattern and the occurrences of another
- The descent statistic on 123-avoiding permutations
- The insertion encoding of permutations
- The joint distribution of consecutive patterns and descents in permutations avoiding 3-1-2
- Three-letter-pattern avoiding permutations and functional equations
- Total occurrence statistics on restricted permutations
Cited in
(10)- Equidistributions of Mahonian statistics over pattern avoiding permutations
- Counting pattern avoiding permutations by number of movable letters
- Subregularity in infinitely labeled generating trees of restricted permutations
- The equidistribution of some length-three vincular patterns on \(S_n(132)\)
- Automatic discovery of structural rules of permutation classes
- Distributions of statistics over pattern-avoiding permutations
- Refining enumeration schemes to count according to the inversion number
- Visibility in pattern-restricted permutations
- Refined consecutive pattern enumeration via a generalized cluster method
- Unimodal permutations and almost-increasing cycles
This page was built for publication: Refining enumeration schemes to count according to permutation statistics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405263)
