Bijections between pattern-avoiding derangements and desarrangements

Abstract

Derangements are permutations without fixed points, and are in bijection with desarrangements: permutations whose first non-descent is even, or equivalently, permutations without ``pixed points''. Bsila, Cox, Hugo, Styron, and Zhuang recently proved a theorem characterizing all $\Pi \subseteq {\mathfrak{S}}_3$, such that $1\le \left|\Pi \right|\le 3$, for which the number of derangements avoiding all patterns in $\Pi$ is equal to the number of desarrangements avoiding all patterns in $\Pi$. They left finding a bijective proof of this theorem as an open problem, and posed a related conjecture concerning the distributions of fixed points and pixed points over pattern avoidance classes. In this paper, we give bijective proofs of this theorem and conjecture.

21 pages