Martin Rubey - Nestings of Matchings and Permutations and North Steps in PDSAWs

dmtcs:3611 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) - https://doi.org/10.46298/dmtcs.3611
Nestings of Matchings and Permutations and North Steps in PDSAWsConference paper

Authors: Martin Rubey 1

  • 1 Fakultät für Mathematik [Wien]


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


Volume: DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] nestings and crossings of matchings and permutations, PDSAWs

1 Document citing this article

Consultation statistics

This page has been seen 327 times.
This article's PDF has been downloaded 326 times.