Bijections for refined restricted permutations
The contribution of the authors is a bijective proof of a strengthening of a recent result of \textit{A. Robertson} et al. [Ann. Comb. 6, 427--444 (2002; Zbl 1017.05014)] and \textit{S. Elizade} [Proc. FPSAC 2003] about the number of \(321\)- and \(132\)-avoiding permutations. A permutation \(\sigma=(\sigma(1),\sigma(2),\dots,\sigma(n))\in {\mathcal S}_n\) is said to contain another permutation \(\pi=(\pi(1),\pi(2),\dots,\pi(m))\in {\mathcal S}_m\) if there exist indices \(i_1<i_2<\dots<i_m\) such that \((\sigma(i_1),\sigma(i_2),\dots,\sigma(i_m))\) is in the same relative order as \((\pi(1),\pi(2),\dots,\pi(m))\). If \(\sigma\) does not contain \(\pi\), then \(\sigma\) is called \(\pi\)-avoiding. For \(\sigma\in {\mathcal S}_n\) let \(\text{fp}(\sigma)\) (\(\text{exc}(\sigma)\)) denote the number of \(i\in \{1,2,\dots,n\}\) with \(\sigma(i)=i\) (with \(\sigma(i)>i\)). Furthermore, let \(\text{lis}(\sigma)\) denote the length of a longest increasing subsequence and \(\text{rank}(\sigma)\) denote the largest \(k\) such that \(\sigma(i)>k\) for all \(i\leq k\). The authors establish a bijection between the set of \(321\)-avoiding permutations \(\sigma\in {\mathcal S}_n\) with \(\text{fp}(\sigma)=i\), \(\text{exc}(\sigma)=j\) and \(\text{lis}(\sigma)=k\) and the set of \(132\)-avoiding permutations \(\sigma\in {\mathcal S}_n\) with \(\text{fp}(\sigma)=i\), \(\text{exc}(\sigma)=j\) and \(\text{rank}(\sigma)=n-k\) for any \(0\leq i,j,k\leq n\). The fact that the number of \(321\)-avoiding permutations \(\sigma\in {\mathcal S}_n\) with \(\text{fp}(\sigma)=i\) and \(\text{exc}(\sigma)=j\) and the number of \(132\)-avoiding permutations \(\sigma\in {\mathcal S}_n\) with \(\text{fp}(\sigma)=i\) and \(\text{exc}(\sigma)=j\) are equal was proved by Robertson et al. and Elizade using technically more involved methods.
- On bijections for pattern-avoiding permutations
- On two bijections from \(S_{n}(321)\) to \(S_{n}(132)\).
- Another look at bijections for pattern-avoiding permutations
- Classification of bijections between 321- and 132-avoiding permutations
- Classification of bijections between 321- and 132-avoiding permutations
- A survey of the Fine numbers
- Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three
- Fixed points and excedances in restricted permutations
- Generating trees and the Catalan and Schröder numbers
- scientific article; zbMATH DE number 4168687 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 1033382 (Why is no real title available?)
- Longest Increasing and Decreasing Subsequences
- Longest increasing subsequences in pattern-restricted permutations
- On the diagram of 132-avoiding permutations
- Permutations with restricted patterns and Dyck paths
- Refined restricted permutations
- Restricted permutations
- On bijections for pattern-avoiding permutations
- A generalization of Simion-Schmidt's bijection for restricted permutations
- A sextuple equidistribution arising in pattern avoidance
- Restricted simsun permutations
- Pattern avoidance in matchings and partitions
- Crossings and nestings over some Motzkin objects and \(q\)-Motzkin numbers
- Refined Wilf-equivalences by Comtet statistics
- A combinatorial bijection on di-sk trees
- Exact and asymptotic enumeration of cyclic permutations according to descent set
- A distributive lattice structure connecting Dyck paths, noncrossing partitions and 312-avoiding permutations
- Two descent statistics over \(321\)-avoiding centrosymmetric involutions
- A Bijection in the Theory of Derangements
- Inversion polynomials for 321-avoiding permutations
- The shape of random pattern-avoiding permutations
- Permutation patterns and statistics
- Impulse parameter and a new equivalence between 123- and 132-avoiding permutations
- Descent sets on 321-avoiding involutions and hook decompositions of partitions
- Classification of bijections between 321- and 132-avoiding permutations
- Bijective enumeration of permutations starting with a longest increasing subsequence
- Fixed points of 321-avoiding permutations
- Bijections for restricted inversion sequences and permutations with fixed points
- Pattern avoidance and Young tableaux
- Crossings over permutations avoiding some pairs of patterns of length three
- \(k\)-arrangements, statistics, and patterns
- scientific article; zbMATH DE number 3895076 (Why is no real title available?)
- Counting permutations with no long monotone subsequence via generating trees and the kernel method
- Refined sign-balance on 321-avoiding permutations
- Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
- scientific article; zbMATH DE number 7666236 (Why is no real title available?)
- The Schützenberger involution over Dyck paths
- The degree of asymmetry of sequences
- Enumerating two permutation classes by the number of cycles
- A bijection for length-5 patterns in permutations
- Rowmotion on 321-avoiding permutations
- A bijection between evil-avoiding and rectangular permutations
- Fixed points and excedances in restricted permutations
- Pattern-avoiding permutations and Brownian excursion. II: Fixed points
- Rowmotion on 321-avoiding permutations
- Parity statistics on restricted permutations and the Catalan-Schett polynomials
- On (joint) equidistributions of mesh patterns 123 and 132 with symmetric shadings
- Generalized statistics on \(S_{n}\) and pattern avoidance
- Restricted permutations refined by number of crossings and nestings
- Restricted Dumont permutations, Dyck paths, and noncrossing partitions
- Inversion formulae on permutations avoiding 321
- A history and a survey of lattice path enumeration
- Another look at bijections for pattern-avoiding permutations
This page was built for publication: Bijections for refined restricted permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598452)
