Mesh patterns and the expansion of permutation statistics as sums of permutation patterns

MaRDI QIDQ540135zbMATH OpenFDO

Authors Petter Brändén, Anders Claesson

Publication date 1 June 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.4226, https://eudml.org/doc/228398, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i2p5.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Andre permutationsdescentsexcedancesleft-to-right maximaMahonian staticticsmajor indexmesh patternspermutation patternpermutation statisticssimsun permutationsstrong fixed points

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19)

Abstract: Any permutation statistic $f:symoCC$ may be represented uniquely as a, possibly infinite, linear combination of (classical) permutation patterns: $f=Sigm{a}_{a}ulambd{a}_f(au)au$. To provide explicit expansions for certain statistics, we introduce a new type of permutation patterns that we call mesh patterns. Intuitively, an occurrence of the mesh pattern $p=(pi,R)$ is an occurrence of the permutation pattern $pi$ with additional restrictions specified by $R$ on the relative position of the entries of the occurrence. We show that, for any mesh pattern $p=(pi,R)$, we have $lambd{a}_p(au)=(-1{)}^{|au|-|pi|}{p}^{star}(au)$ where $p^{star}=(pi,R^c)$ is the mesh pattern with the same underlying permutation as $p$ but with complementary restrictions. We use this result to expand some well known permutation statistics, such as the number of left-to-right maxima, descents, excedances, fixed points, strong fixed points, and the major index. We also show that alternating permutations, Andr'e permutations of the first kind and simsun permutations occur naturally as permutations avoiding certain mesh patterns. Finally, we provide new natural Mahonian statistics.

Recommendations

• Generalized permutation patterns and a classification of the Mahonian statistics
• Variations on descents and inversions in permutations
• Distributions of several infinite families of mesh patterns
• Distributions of mesh patterns of short lengths
• Simple marked mesh patterns

Cited in

(55)

• Generalized permutation patterns and a classification of the Mahonian statistics
• An a priori harmonic mesh for singularly perturbed boundary value problems
• An \(O(n^2\log m)\)-time algorithm for the boxed-mesh permutation pattern matching problem
• Reduced word manipulation: patterns and enumeration
• Equidistributions of mesh patterns of length two and Kitaev and Zhang's conjectures
• Transport of patterns by Burge transpose
• Weak ascent sequences and related combinatorial structures
• From Hertzsprung's problem to pattern-rewriting systems
• Pattern-functions, statistics, and shallow permutations
• Asymptotic behaviour of the containment of certain mesh patterns
• The poset of mesh patterns
• Sorting with pattern-avoiding stacks: the 132-machine
• Stack-sorting preimages of permutation classes
• Distributions of several infinite families of mesh patterns
• Distributions of mesh patterns of short lengths
• Frame patterns in \(n\)-cycles
• \((a, b)\)-rectangle patterns in permutations and words
• Counting permutations by simsun successions
• Restricted non-separable planar maps and some pattern avoiding permutations
• Noncontiguous pattern containment in binary trees
• \(k\)-pop stack sortable permutations and \(2\)-avoidance
• Principal specializations of Schubert polynomials and pattern containment
• Equidistributions of mesh patterns of length two
• The peak statistics on simsun permutations
• Improved algorithms for the boxed-mesh permutation pattern matching problem
• Permutation classes and polyomino classes with excluded submatrices
• Harmonic numbers, Catalan's triangle and mesh patterns
• Shape-Wilf-equivalences for vincular patterns
• Refined enumeration of permutations sorted with two stacks and a D₈-symmetry
• About half permutations
• Word-Representable Graphs: a Survey
• Sorting Cayley permutations with pattern-avoiding machines
• Transformation à la Foata for special kinds of descents and excedances
• Combinatorial generation via permutation languages. I: Fundamentals
• Algorithmic coincidence classification of mesh patterns
• Positional Marked Patterns in Permutations
• scientific article; zbMATH DE number 7765381 (Why is no real title available?)
• Singleton mesh patterns in multidimensional permutations
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Stanley-Wilf limits for patterns in rooted labeled forests
• Turning cycle restrictions into mesh patterns via Foata's fundamental transformation
• Prism permutations in the Bruhat order
• Combinatorial generation via permutation languages. VI: Binary trees
• Composable constraint models for permutation enumeration
• Stack-sorting with stacks avoiding vincular patterns
• Joint equidistributions of mesh patterns 123 and 132 with minus antipodal shadings
• Distributions of mesh patterns of short lengths on king permutations
• Self-modified difference ascent sequences
• Pattern-avoiding binary trees -- generation, counting, and bijections
• On a conjecture on pattern-avoiding machines
• Combinatorics of rectangulations: old and new bijections
• On (joint) equidistributions of mesh patterns 123 and 132 with symmetric shadings
• Between weak and Bruhat: the middle order on permutations
• Mesh patterns with superfluous mesh
• Wilf-classification of mesh patterns of short length

This page was built for publication: Mesh patterns and the expansion of permutation statistics as sums of permutation patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q540135)