Journal of Integer Sequences, Vol. 26 (2023), Article 23.8.5

Restricting Dyck Paths and 312-Avoiding Permutations


Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani
Dipartimento di Matematica e Informatica "Ulisse Dini"
Università di Firenze
Viale G. B. Morgagni 65
50134 Firenze
Italy

Abstract:

We interpret Dyck paths of height at most h and without valleys at height h – 1 combinatorially, by means of 312-avoiding permutations with some restrictions on their left-to-right maxima. We obtain our results by analyzing a restriction of a well-known bijection between the sets of Dyck paths and 312-avoiding permutations. We also provide a recursive formula enumerating these two structures by using the ECO method and the theory of production matrices. As a further result we obtain a family of combinatorial identities involving Catalan numbers.


Full version:  pdf,    dvi,    ps,    latex    


(Concerned with sequence A001694.)


Received May 25 2023; revised versions received May 26 2023; September 27 2023; October 5 2023. Published in Journal of Integer Sequences, October 5 2023.


Return to Journal of Integer Sequences home page