On Two Bijections from S_n(321) to S_n(132)

2010/08/26 by Dan Saracino, Saracino, Dan
Computer Science · Engineering · Mathematics · #05A05 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems #math.CO #msc:05A05

paper · pdf · doi:10.48550/arxiv.1008.4557

11 pages, 4 figures

arxiv created 2010/08/26 · openalex publication_date 2010/08/26 · arxiv updated 2010/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let S_n(321) (respectively, S_n(132)) denote the set of all permutations of 1,2,...,n that avoid the pattern 321 (respectively, the pattern 132). Elizalde and Pak gave a bijection Theta from S_n(321) to S_n(132) that preserves the numbers of fixed points and excedances for each element of S_n(321), and commutes with the operation of taking inverses. Bloom and Saracino proved that another bijection Gamma from S_n(321) to S_n(132), introduced by Robertson, has the same properties, and they later gave a pictorial reformulation of Gamma that made these results more transparent. Here we give a pictorial reformulation of Theta, from which it follows that, although the original definitions of Theta and Gamma are very different, these two bijections are in fact related to each other in a very simple way, by using inversion, reversal, and complementation.

Related

• Classification of bijections between 321- and 132-avoiding permutations
• Bijections for refined restricted permutations
• Pattern avoidance and the fundamental bijection
• A note on a bijection for Schröder permutations
• On the diagram of 132-avoiding permutations