<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
A Bijection Between Partially Directed Paths in the SymmetricWedge and Matchings
Svetlana Poznanović
Department of Mathematics, Texas A&M University, College Station, TX 77843, USA
Annals of Combinatorics 15 (2) pp.331-339 April, 2011
AMS Subject Classification: 05A16; 60C05, 60F05
We give a bijection between partially directed paths in the symmetric wedge y = ±x and matchings, which sends north steps to nestings. This gives a bijective proof of a result of Janse van Rensburg, Prellberg, and Rechnitzer that was first discovered through the corresponding generating functions: The number of partially directed paths starting at the origin confined to the symmetric wedge y = ±x with k north steps is equal to the number of matchings on [2n] with k nestings.
Keywords: partially directed path, matching, nesting


1. Janse van Rensburg, E.J.J., Prellberg, T., Rechnitzer, A.: Partially directed paths in a wedge. J. Combin. Theory Ser. A 115(4), 623–650 (2008)

2. Kasraoui, A., Zeng, J.: Distribution of crossings, nestings and alignments of two edges in matchings and partitions. Electron. J. Combin. 13(1), #R33 (2006)

3. Klazar, M.: On identities concerning the numbers of crossings and nestings of two edges in matchings, SIAM J. Discrete Math. 20(4), 960–976 (2006)

4. Poznanovi´c, S., Yan, C.: Crossings and nestings of two edges in set partitions, SIAM J. Discrete Math. 23(2), 787–804 (2009)

5. Riordan, J.: The distribution of crossings of chords joining pairs of 2n points on a circle. Math. Comp. 29, 215–222 (1975)

6. Rubey, M.: Nestings of matchings and permutations and north steps in PDSAWs. In: 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), pp. 691–704. Assoc. Discrete Math. Theor. Comput. Sci., Nancy (2008)

7. de Sainte-Catherine, M.: Couplages et pfaffiens en combinatoire, physique et informatique. PhD thesis, University of Bordeaux I, Talence (1983)

8. Touchard, J.: Sur un probl`eme de configurations et sur les fractions continues, Canadian J. Math. 4, 2–25 (1952)