Séminaire Lotharingien de Combinatoire, B60d (2008), 30 pp.
Anders Claesson and Sergey Kitaev
Classification of Bijections Between 321- and 132-Avoiding Permutations
It is well-known, and was first established by Knuth in 1969, that
the number of 321-avoiding permutations is equal to that of
132-avoiding permutations. In the literature one can find many
subsequent bijective proofs of this fact. It turns out that some of
the published bijections can easily be obtained from others. In this
paper we describe all bijections we were able to find in the
literature and show how they are related to each other via
"trivial" bijections. We classify the bijections according to
statistics preserved (from a fixed, but large, set of statistics),
obtaining substantial extensions of known results. Thus, we give a
comprehensive survey and a systematic analysis of these bijections.
We also give a recursive description of the algorithmic bijection
given by Richards in 1988 (combined with a bijection by Knuth from
1969). This bijection is equivalent to the celebrated bijection of
Simion and Schmidt (1985), as well as to the bijection given by
Krattenthaler in 2001, and it respects 11 statistics - the largest
number of statistics any of the bijections respects.
Received: May 19, 2008.
Accepted: October 19, 2008.
Final Version: November 4, 2008.
The following versions are available: