Refining enumeration schemes to count according to permutation statistics
From MaRDI portal
Publication:405263
zbMATH Open1300.05026arXiv1401.0337MaRDI QIDQ405263FDOQ405263
Publication date: 4 September 2014
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1401.0337
File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)
Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finding regular insertion encodings for permutation classes
- Enumeration schemes and, more importantly, their automatic generation
- Restricted permutations
- Permutations with restricted patterns and Dyck paths
- Generalized permutation patterns and a classification of the Mahonian statistics
- Partially ordered generalized patterns
- Permutation patterns and statistics
- Generalized pattern avoidance
- Enumeration Schemes for Restricted Permutations
- Enumeration schemes for permutations avoiding barred patterns
- Refining enumeration schemes to count according to the inversion number
- Shape-Wilf-equivalences for vincular patterns
- Enumeration schemes for vincular patterns
- Some permutations with forbidden subsequences and their inversion number
- Surprising symmetries in objects counted by Catalan numbers
- Expected patterns in permutation classes
- Restricted 1-3-2 permutations and generalized patterns
- Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations
- Three-letter-pattern avoiding permutations and functional equations
- The insertion encoding of permutations
- Total occurrence statistics on restricted permutations
- The absence of a pattern and the number of occurrences of another
- The descent statistic on 123-avoiding permutations
- The joint distribution of consecutive patterns and descents in permutations avoiding 3-1-2
Cited In (9)
- Automatic discovery of structural rules of permutation classes
- Visibility in pattern-restricted permutations
- Distributions of Statistics over Pattern-Avoiding Permutations
- Subregularity in infinitely labeled generating trees of restricted permutations
- The equidistribution of some length-three vincular patterns on \(S_n(132)\)
- Equidistributions of Mahonian statistics over pattern avoiding permutations
- Counting pattern avoiding permutations by number of movable letters
- Unimodal permutations and almost-increasing cycles
- Refined consecutive pattern enumeration via a generalized cluster method
Uses Software
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)
