Restricted permutations refined by number of crossings and nestings

DOI10.1016/J.DISC.2020.111950MaRDI QIDQ776264zbMATH OpenOpenAlexFDO

Authors Paul M. Rakotomamonjy

Publication date 8 July 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

\(q\)-Catalan numbersbijectionscrossingsnestingsrestricted permutationsWilf-equivalence

Mathematics Subject Classification ID

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

Abstract: Let $st=s{t}_1,ldots,s{t}_k$ be a set of $k$ statistics on permutations with $kgeq1$. We say that two given subset of permutations $T$ and $T^{\prime }$ are $st$-Wilf-equivalent if the joint distributions of all statistics in $st$ over the sets of $T$-avoiding permutations $S_n(T)$ and $T^{\prime }$-avoiding permutations $S_n(T^{\prime })$ are the same. The main purpose of this paper is the (cr,nes)-Wilf-equivalence classes for all single patterns in $S_3$, where cr and nes denote respectively the statistics number of crossings and nestings. One of the main tools that we use is the bijection $Theta:S_n(321)ightarrow{S}_n(132)$ which was originally exhibited by Elizalde and Pak in cite{ElizP}. They proved that the bijection $Theta$ preserves the number of fixed points and excedances. Since the given formulation of $Theta$ is not direct, we show that it can be defined directly by a recursive formula. Then, we prove that it also preserves the number of crossings. Due to the fact that the sets of non-nesting permutations and 321-avoiding permutations are the same, these properties of the bijection $Theta$ leads to an unexpected result related to the q,p-Catalan numbers of Randrianarivony defined in cite{ARandr}.

Recommendations

• On k-crossings and k-nestings of permutations
• Bijections for refined restricted permutations
• On bijections for pattern-avoiding permutations
• On two bijections from \(S_{n}(321)\) to \(S_{n}(132)\).
• Crossings over permutations avoiding some pairs of patterns of length three

Cites work

• q,p-Catalan numbers
• A simple and unusual bijection for Dyck paths and its consequences
• Another look at bijections for pattern-avoiding permutations
• Bijections for refined restricted permutations
• Classification of bijections between 321- and 132-avoiding permutations
• Continued fractions, \(q\)-Catalan numbers, and \(q\)-Genocchi polynomials
• Crossings and alignments of permutations
• Fixed points and excedances in restricted permutations
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• Multiple pattern avoidance with respect to fixed points and excedances
• On a recurrence related to 321 -- avoiding permutations
• On bijections for pattern-avoiding permutations
• On k-crossings and k-nestings of permutations
• On two bijections from \(S_{n}(321)\) to \(S_{n}(132)\).
• Permutation patterns and statistics
• Permutations with restricted patterns and Dyck paths
• Refined restricted permutations
• Restricted permutations
• Restricted permutations from Catalan to Fine and back

Cited in

(3)

• Crossings and nestings over some Motzkin objects and \(q\)-Motzkin numbers
• On k-crossings and k-nestings of permutations
• Crossings over permutations avoiding some pairs of patterns of length three

Describes a project that uses

Uses Software

• AARON

This page was built for publication: Restricted permutations refined by number of crossings and nestings

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