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

major indexdescentsexcedancessimsun permutationspermutation patternpermutation statisticsmesh patternsleft-to-right maximaAndre permutationsMahonian staticticsstrong 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

(45)

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

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)