DMTCS Proceedings, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)

Font Size:  Small  Medium  Large

Nestings of Matchings and Permutations and North Steps in PDSAWs

Martin Rubey

Abstract


We present a simple bijective proof of the fact that matchings of [2n] with N nestings are equinumerous to partially directed self avoiding walks confined to the symmetric wedge defined by y=±x, with n east steps and N north steps. A very similar construction connects permutations with N nestings and PDSAWs remaining below the x-axis, again with N north steps. Furthermore, both bijections transport several combinatorially meaningful parameters.

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional