Restricted \(123\)-involutions (Q697102)

This paper studies the enumeration of involutions of length \(n\) avoiding (or containing exactly once) 132 and avoiding (or containing exactly once) an arbitrary permutation \(\tau\) of length \(k\). A permutation \(\pi\) is said to contain \(\tau\) if there exists a subsequence \(1\leq i_1< i_2<\cdots< i_k\leq n\) such that \((\pi_{i_1},\dots, \pi_{i_k})\) is order-isomorphic to \(\tau\). The methods used by the authors enable them to include many of the previously known results for this kind of problem as well as many new results. Several different cases of \(\tau\) are discussed, including: \(\tau= 12\dots k\), \(\tau= 2134\dots k\); \(\tau\) an extended double-wedge pattern. A bijection between involutions avoiding both \(132\) and \(12\dots k\) and involutions avoiding both \(132\) and \(2134\dots k\) is given, and it is shown that involutions avoiding both 132 and any extended double-wedge pattern of length \(k\) are equinumerous with involutions avoiding \(132\) and \(12\dots k\). An example of a result concerning involutions containing \(132\) exactly once is the following. Involutions of length \(n\) containing \(132\) exactly once and having \(p\) fixed points are equinumerous with involutions of length \(n-2\) avoiding \(132\) and having \(p\) fixed points; their number is the ballot number \(\left(\begin{smallmatrix} n-2\\ {1\over 2}(n+ p)-1\end{smallmatrix}\right)- \left(\begin{smallmatrix} n-2\\ {1\over 2}(n+ p)\end{smallmatrix}\right)\).