Turning cycle restrictions into mesh patterns via Foata's fundamental transformation

DOI10.1016/J.DISC.2023.113826MaRDI QIDQ6177428zbMATH OpenOpenAlexFDO

Authors Anders Claesson, Henning Úlfarsson

Publication date 17 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.17931

zbMATH Keywords

Foata's fundamental transformationgenerating functionmesh patternpermutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: An adjacent $q$-cycle is a natural generalization of an adjacent transposition. We show that the number of adjacent $q$-cycles in a permutation maps to the sum of occurrences of two mesh patterns under Foata's fundamental transformation. As a corollary we resolve Conjecture 3.14 in the paper ``From Hertzprung's problem to pattern-rewriting systems by the first author.

Review text

This article gives the generating function for the number of permutations avoiding a certain mesh pattern, solving a conjecture of the first author [Algebr. Comb. 5, No. 6, 1257--1277 (2022; Zbl 1504.05008)]. The key idea is the use of Foata's fundamental transformation [\textit{D. Foata}, Publ. Inst. Stat. Univ. Paris 14, 81--241 (1965; Zbl 0133.41304)], which gives a bijection that maps the major index to the inversion number.

Recommendations

• Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
• Distributions of mesh patterns of short lengths
• Distributions of several infinite families of mesh patterns
• Equidistributions of mesh patterns of length two
• Inversion generating functions for signed pattern avoiding permutations

Cites work

• Adjacent \(q\)-cycles in permutations
• From Hertzsprung's problem to pattern-rewriting systems
• scientific article; zbMATH DE number 3216769 (Why is no real title available?)
• Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
• Wilf-classification of mesh patterns of short length

Cited in

(2)

• Pattern avoidance and the fundamental bijection
• Pattern-restricted one-cycle permutations with a pattern-restricted cycle form

This page was built for publication: Turning cycle restrictions into mesh patterns via Foata's fundamental transformation

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