On Refinements of Wilf-Equivalence for Involutions

Abstract

Let ${\mathcal{S}}_n(\pi )$ (resp. ${\mathcal{I}}_n(\pi )$ and ${\mathcal{A}\mathcal{I}}_n(\pi )$) denote the set of permutations (resp. involutions and alternating involutions) of length $n$ which avoid the permutation pattern $\pi$. For $k,m\ge 1$, Backelin-West-Xin proved that $|{\mathcal{S}}_n(12\cdots k\tau )|=|{\mathcal{S}}_n(k\cdots 21\tau )|$ by establishing a bijection between these two sets, where $\tau ={\tau }_1{\tau }_2\cdots {\tau }_m$ is an arbitrary permutation of $k+1,k+2,\dots ,k+m$. The result has been extended to involutions by Bousquet-Mélou and Steingrímsson and to alternating permutations by the first author. In this paper, we shall establish a peak set preserving bijection between ${\mathcal{I}}_n(123\tau )$ and ${\mathcal{I}}_n(321\tau )$ via transversals, matchings, oscillating tableaux and pairs of noncrossing Dyck paths as intermediate structures. Our result is a refinement of the result of Bousquet-Mélou and Steingrímsson for the case when $k=3$. As an application, we show bijectively that $|{\mathcal{A}\mathcal{I}}_n(123\tau )|=|{\mathcal{A}\mathcal{I}}_n(321\tau )|$, confirming a recent conjecture of Barnabei-Bonetti-Castronuovo-Silimbani. Furthmore, some conjectured equalities posed by Barnabei-Bonetti-Castronuovo-Silimbani concerning pattern avoiding alternating involutions are also proved.

31 pages, 12 figures