Affiliations: [a] Institut de Recherche en Informatique Fondamentale (IRIF), Université Paris Diderot, Paris, France. Enrica.Duchi@irit.univ-paris-diderot.fr | [b] Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche, Università di Siena, Siena, Italy. guerrini55@student.unisi.it | [c] Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche, Università di Siena, Siena, Italy. rinaldi@unisi.it
Correspondence:
[*]
Address for correspondence: Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche, Università di Siena, Siena, Italy
Abstract: In this paper we study the family of permutations avoiding the pattern 122+3 (trivially equivalent to those avoiding 123⎵4), which extend the popular 123-avoiding permutations. In particular we provide an algorithmic description of a generating tree for these permutations, that is a way to build every object of a given size n + 1 in a unique way by performing local modifications on an object of size n. Our algorithm leads to a direct bijection between 123⎵4-avoiding permutations and valley-marked Dyck paths. It extends a known bijection between 123-avoiding permutations and Dyck paths, and makes explicit the connection between these objects that was earlier obtained by Callan through a series of non-trivial bijective steps. In particular our construction is simple enough to allow for efficient exhaustive generation.
