Source-linked AI summary
Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
Petter Brändén, Anders Claesson
TL;DR
Mesh patterns extend classical patterns with restrictions on the relative positions of occurrence entries, providing a framework for expanding permutation statistics. The paper’s reciprocity result relates those expansions to complementary restrictions and characterizes several permutation classes by pattern avoidance.
Problem
The paper seeks a way to describe pattern-expansion coefficients for mesh patterns, motivating a pattern family closed under complementary restrictions.
Source: §2 · p. 3Method
The paper introduces mesh patterns and proves a reciprocity theorem relating their expansion coefficients to occurrences of patterns with complementary restrictions.
Source: §1.1 · p. 1, §2 · p. 3Results
Takeaways & Limitations
Complementary restrictions provide the pattern closure needed to describe coefficients in expansions of generalized permutation patterns.
Source: §2 · p. 3
Abstract
from arXiv · showhide
Any permutation statistic $f:\sym\to\CC$ may be represented uniquely as a, possibly infinite, linear combination of (classical) permutation patterns: $f= \Sigma_\tau\lambda_f(\tau)\tau$. 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 $\lambda_p(\tau) = (-1)^{|\tau|-|\pi|}p^{\star}(\tau)$ 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.
1. Introduction
The introduction defines mesh patterns as classical patterns with restrictions on where other entries may occur, then places them in a framework where permutation statistics have unique pattern expansions.
1.1. Mesh patterns.
- A mesh pattern pairs a permutation with restricted grid regions that an occurrence in another permutation must leave empty.The restrictions are imposed on a classical occurrence of the underlying permutation.Source: §1.1 · pp. 1–2
- Classical, vincular, and bivincular patterns are special cases of mesh patterns, distinguished by which grid regions are restricted.Barred patterns with one barred letter can also be represented as mesh patterns.Source: §1.1 · p. 2
- Permutations encoding saturated chains in the composition analogue of Young’s lattice are characterized by avoiding mesh patterns.The associated tree condition concerns vertices off the leftmost branch that have two sons.Source: §1.1 · p. 2
- The displayed identities express left-to-right maxima, inversions, descents, and components using permutation patterns.The passages name the statistics but do not preserve the full displayed formulas.Source: §1.1 · pp. 2–3
1.2. Permutation statistics and an incidence algebra.
- Every permutation statistic has a unique, typically infinite, formal linear combination of classical patterns.The incidence-algebra formulation expresses its coefficients using the inverse of P.Source: §1.2 · p. 3
2. The Reciprocity Theorem
The Reciprocity Theorem gives the pattern-expansion coefficients of a mesh pattern using its complementary restrictions. Its proof isolates the occurrences that survive cancellation, and a corollary gives the inverse of P.
2. The Reciprocity Theorem
- The reciprocity formula relates a mesh pattern’s coefficients to occurrences of the pattern with complementary restrictions, with a sign depending on the size difference.The complementary pattern keeps the same underlying permutation and replaces the restricted regions by their complement.Source: §2 · pp. 3–4
- In the proof, contributions cancel unless the selected occurrence has no eligible extra elements, leaving occurrences of the complementary mesh pattern.The eligible elements lie in squares not indexed by the original restrictions.Source: §2 · p. 4
- A corollary states the inverse of P in the incidence algebra.The corollary follows by applying reciprocity to a fully restricted mesh pattern whose complement is classical.Source: §2 · p. 4
3. Expansions of some permutation statistics
The section expresses the major index through mesh-pattern terms and develops an involution for coefficients in the excedance expansion. It also gives a piecewise form for the major-index coefficients.
3. Expansions of some permutation statistics
- The major index is expressed as a sum of mesh-pattern terms, with its coefficient function simplifying to a piecewise rule.The rule assigns 1 to π = 21, alternating signs under two stated inequalities, and 0 otherwise.Source: §3 · pp. 4–5
- The section defines left-to-right maxima, fixed points, excedance tops, and strong and skew strong fixed points through the Q-region sets.It also defines excess as |Q4(π; x)| − |Q2(π; x)| and counts entries of each excess with exck(π).Source: §3 · p. 5
- A sign-reversing involution pairs non-fixed subwords of equal excess, leaving skew strong fixed points to determine the excedance coefficient.The involution toggles α(x) in or out of the subword; its fixed points have Q1(x) = Q3(x) = ∅.Source: §3 · p. 6
4. Euler numbers
The section characterizes alternating, André, and simsun permutations through avoidance of specified vincular or mesh patterns. It connects these classes to Euler-number counts and recurrences.
4. Euler numbers
- Alternating permutations are exactly those avoiding the stated vincular or mesh patterns, and their number in Sn is the Euler number En.The avoidance characterization is given in mesh-pattern terms.Source: §4 · p. 7
- Simsun permutations are characterized by avoiding a mesh pattern and are counted by E_{n+1} in Sn.The definition also requires that deleting the i largest letters leaves no double descents for every 1 ≤ i ≤ n.Source: §4 · p. 7
- André permutations of the first kind are characterized by avoidance of specified patterns and have cardinality E_{n+1} in Sn.Their avoidance class has the same recursive description as André permutations of the first kind.Source: §4 · pp. 7–8
- Lemma 6 immediately yields a version of the Euler-number recursion formula.The section also reports that, up to trivial symmetries, only simsun and André are 321-mesh-pattern classes counted by E_{n+1} for all n.Source: §4 · p. 8
5. New Mahonian Statistics
The section constructs Mahonian statistics by mixing decompositions of inversions and non-inversions, then introduces mix′ through a computer search and proves it Mahonian.
- The mix decompositions split inversions by whether they serve as 21 in a 213, and non-inversions by whether they serve as 12 in a 123.Source: §5 · p. 8
- For mix, the argument seeks a bijection matching |A+(ψ(π))| to |I+(π)| while fixing |A−|, and proves the stronger ca/ci swap.Source: §5 · pp. 8–9
- A computer search found one new Mahonian statistic beyond mix, up to trivial symmetries; mix′ is Mahonian by symmetry of the recursion variables.Source: §5 · pp. 9–10