Permutation patterns and statistics
From MaRDI portal
Abstract: Let S_n denote the symmetric group of all permutations of the set {1, 2, ...,n} and let S = cup_{nge0} S_n. If Pi is a set of permutations, then we let Av_n(Pi) be the set of permutations in S_n which avoid every permutation of Pi in the sense of pattern avoidance. One of the celebrated notions in pattern theory is that of Wilf-equivalence, where Pi and Pi' are Wilf equivalent if #Av_n(Pi)=#Av_n(Pi') for all nge0. In a recent paper, Sagan and Savage proposed studying a q-analogue of this concept defined as follows. Suppose st:S->N is a permutation statistic where N represents the nonnegative integers. Consider the corresponding generating function, F_n^{st}(Pi;q) = sum_{sigma in Av_n(Pi)} q^{st sigma}, and call Pi,Pi' st-Wilf equivalent if F_n^{st}(Pi;q)=F_n^{st}(Pi';q) for all nge0. We present the first in-depth study of this concept for the inv and maj statistics. In particular, we determine all inv- and maj-Wilf equivalences for any Pi containd in S_3. This leads us to consider various q-analogues of the Catalan numbers, Fibonacci numbers, triangular numbers, and powers of two. Our proof techniques use lattice paths, integer partitions, and Foata's fundamental bijection. We also answer a question about Mahonian pairs raised in the Sagan-Savage article.
Recommendations
Cites work
- scientific article; zbMATH DE number 3887638 (Why is no real title available?)
- scientific article; zbMATH DE number 3456973 (Why is no real title available?)
- A relationship between the major index for tableaux and the charge statistic for permutations
- A simple and unusual bijection for Dyck paths and its consequences
- Bijections for refined restricted permutations
- Congruences for Catalan and Motzkin numbers and related sequences
- Fixed points and excedances in restricted permutations
- Generalized permutation patterns and a classification of the Mahonian statistics
- Generating trees and the Catalan and Schröder numbers
- Inversion polynomials for 321-avoiding permutations
- Multiple pattern avoidance with respect to fixed points and excedances
- On the Netto Inversion Number of a Sequence
- Restricted permutations
- Set partition statistics and \(q\)-Fibonacci numbers
- The \(q,t\)-Catalan numbers and the space of diagonal harmonics. With an appendix on the combinatorics of Macdonald polynomials
- Two element lattice permutation numbers and their \(q\)-generalization
Cited in
(44)- Eulerian pairs on Fibonacci words
- Profiles of permutations
- Expected patterns in permutation classes
- Mahonian pairs
- Descent sets on 321-avoiding involutions and hook decompositions of partitions
- Pattern-avoiding polytopes
- A \(q=-1\) phenomenon for pattern-avoiding permutations
- Revisiting pattern avoidance and quasisymmetric functions
- Refining enumeration schemes to count according to permutation statistics
- A lifting of the Goulden-Jackson cluster method to the Malvenuto-Reutenauer algebra
- Shuffle-compatible permutation statistics
- Restricted growth function patterns and statistics
- Generalized statistics on \(S_{n}\) and pattern avoidance
- Crossings over permutations avoiding some pairs of patterns of length three
- Equidistribution of set-valued statistics on standard Young tableaux and transversals
- A sextuple equidistribution arising in pattern avoidance
- Descent c-Wilf equivalence
- Increasing spanning forests in graphs and simplicial complexes
- Major index distribution over permutation classes
- On the parity of certain coefficients for a \(q\)-analogue of the Catalan numbers
- More statistics on permutation pairs
- Operators of equivalent sorting power and related Wilf-equivalences
- Set partition patterns and the dimension index
- Pattern statistics and Vandermonde matrices.
- An infinite family of inv-Wilf-equivalent permutation pairs
- scientific article; zbMATH DE number 5870282 (Why is no real title available?)
- Inversion polynomials for 321-avoiding permutations
- Refined enumeration of permutations sorted with two stacks and a D₈-symmetry
- The equidistribution of some Mahonian statistics over permutations avoiding a pattern of length three
- Refined Wilf-equivalences by Comtet statistics
- Further refinements of Wilf-equivalence for patterns of length 4
- Restricted permutations refined by number of crossings and nestings
- Equidistributions of Mahonian statistics over pattern avoiding permutations
- Interview with Bruce Sagan
- Unimodal permutations and almost-increasing cycles
- On a refinement of Wilf-equivalence for permutations
- Cyclic pattern containment and avoidance
- A refinement of Wilf-equivalence for patterns of length 4
- Inversion polynomials for permutations avoiding consecutive patterns
- Distributions of statistics over pattern-avoiding permutations
- Permutation statistics and multiple pattern avoidance
- Descents and des-Wilf equivalence of permutations avoiding certain nonclassical patterns
- Inversion formulae on permutations avoiding 321
- Further bijections to pattern-avoiding valid hook configurations
This page was built for publication: Permutation patterns and statistics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q449114)
