Bijections for refined restricted permutations (Q598452): Difference between revisions

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.