Appeared in Annals of Combinatorics v. 6 (2002), 427-444.
Derangements (and more generally the notion of "fixed points of a permutation") are concepts related to the cycle-structre, i.e. two-line notation, i.e. permutations qua 1-1 functions from [1,n] to [1,n]. On the other hand, Pattern-avoidance (and Wilf- equivalence) are inherently "wordy", i.e. pertain to permutations qua words. Perhaps this is why no one noticed the amazing and easily-stated fact that the number of 132-avoiding derangements equals the number of 321-avoiding derangements, and even more amazingly, that the same is true if you replace "derangement" by "with i fixed points", for ANY $i$ between $0$ and $n$.
This astounding fact was first discovered emprically by Aaron Robertson who also has an even more amazing proposed proof for it, in terms of a beautiful bijection, that in particular gives the best proof todate of the classical Wilf-equivalence result of 321 and 132. But as hard as we tried, we were unable to prove that his bijection preserves the parameter "number of fixed points", even though it certainly does. This bijection that generalizes to other classes, will hopefully form the subject of forthcoming papers by Aaron, and I believe will revolutionize the theory of Wilf-equivalence. Meanwhile we found a more ``pedestrian'' proof, that while somewhat boring to read, was lots of fun to discover, since without Shalosh it would not have been possible. Conversely, as hard as we tried, Shalosh and I were unable to make it completely computational (there must be a tip of a yet-to-be-discovered Ansatz here), and Aaron and Dan provided beautiful human insight to finish it up.
This article contains lots of other neat stuff discovered by Aaron and Dan, and its relation to the the very fine Fine sequence.
This paper is dedicated to the memroy of Rodica Simion (1955-2000), the great enumerator and wonderful human, who, we are sure, would have loved it.
IMPORTANT: This article is accompanied by the Maple package AARON , that emprically confirms many of the results, and that was very instrumental in finding the proofs, but that is not really needed for the proof itself (at least not for checking its formal correctness). It also requires: WILF. Notice that for AARON, the on-line help is ez(); not to interfere with the usual ezra(); that takes care of WILF.
Doron Zeilberger's List of Papers