A Generalization of Simion-Schmidt's Bijection for Restricted Permutations

  • Astrid Reifegerste


We consider the two permutation statistics which count the distinct pairs obtained from the final two terms of occurrences of patterns $\tau_1\cdots\tau_{m-2}m(m-1)$ and $\tau_1\cdots\tau_{m-2}(m-1)m$ in a permutation, respectively. By a simple involution in terms of permutation diagrams we will prove their equidistribution over the symmetric group. As a special case we derive a one-to-one correspondence between permutations which avoid each of the patterns $\tau_1\cdots\tau_{m-2}m(m-1)\in{\cal S}_m$ and those which avoid each of the patterns $\tau_1\cdots\tau_{m-2}(m-1)m\in{\cal S}_m$. For $m=3$ this correspondence coincides with the bijection given by Simion and Schmidt in [Europ. J. Combin. 6 (1985), 383-406].