Pattern avoidance and the fundamental bijection

Abstract

The fundamental bijection is a bijection $\theta :{\mathcal{S}}_n\to {\mathcal{S}}_n$ in which one uses the standard cycle form of one permutation to obtain another permutation in one-line form. In this paper, we enumerate the set of permutations $\pi \in {\mathcal{S}}_n$ that avoids a pattern $\sigma \in {\mathcal{S}}_3$, whose image $\theta (\pi )$ also avoids $\sigma$. We additionally consider what happens under repeated iterations of $\theta$; in particular, we enumerate permutations $\pi \in {\mathcal{S}}_n$ that have the property that $\pi$ and its first $k$ iterations under $\theta$ all avoid a pattern $\sigma$. Finally, we consider permutations with the property that $\pi ={\theta }^2(\pi )$ that avoid a given pattern $\sigma$, and end the paper with some directions for future study.

21 pages