Strathprints logo
Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Classification of bijections between 321- and 132-avoiding permutations

Claesson, Anders and Kitaev, Sergey (2008) Classification of bijections between 321- and 132-avoiding permutations. Séminaire Lotharingien de Combinatoire, 60. ISSN 1286-4889

Full text not available in this repository. (Request a copy from the Strathclyde author)

Abstract

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.

Item type: Article
ID code: 34563
Keywords: bijection, permutation statistics, equidistribution, pattern avoidance, Catalan structures, Electronic computers. Computer science
Subjects: Science > Mathematics > Electronic computers. Computer science
Department: Faculty of Science > Computer and Information Sciences
Related URLs:
Depositing user: Pure Administrator
Date Deposited: 13 Oct 2011 19:25
Last modified: 17 Jul 2013 11:07
URI: http://strathprints.strath.ac.uk/id/eprint/34563

Actions (login required)

View Item