<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue3" %>
A Simple and Unusual Bijection for Dyck Paths and its Consequences
Sergi Elizalde1 and Emeric Deutsch2
1Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
2Polytechnic University, Brooklyn, NY 11201, USA
Annals of Combinatorics 7 (3) p.281-297 September, 2003
AMS Subject Classification: 05A15, 05A05
In this paper we introduce a new bijection from the set of Dyck paths to itself. This bijection has the property that it maps statistics that appeared recently in the study of pattern-avoiding permutations into classical statistics on Dyck paths, whose distribution is easy to obtain. We also present a generalization of the bijection, as well as several applications of it to enumeration problems of statistics in restricted permutations.
Keywords: Dyck paths, bijections, restricted permutations


1. E. Deutsch, Dyck path enumeration, Discrete Math. 204 (1999) 167ĘC202.

2. S. Elizalde, Fixed points and excedances in restricted permutations, preprint, arXiv: math.CO/0212221.

3. S. Elizalde and I. Pak, Bijections for refined restricted permutations, preprint, arXiv: math.CO/0212328.

4. P. Flajolet and R. Sedgewick, Analytic Combinatorics, book in preparation, 1998, Individual chapters are available as INRIA Research Reports 1888, 2026, 2376, 2956, 3162.

5. C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. 27 (2001) 510ĘC530.

6. A. Reifegerste, On the diagram of 132-avoiding permutations, preprint, arXiv: math.CO/0208006.

7. A. Robertson, D. Saracino, and D. Zeilberger, Refined restricted permutations, Ann. Combin. 6 (2002) 427ĘC444.

8. R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison- Wesley, Reading, Massachusetts, 1996.

9. R. Stanley, Enumerative Combinatorics, Vol. I, Cambridge University Press, Cambridge, 1997.