Nestings of Matchings and Permutations and North Steps in PDSAWs

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 permutat...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2008-01, Vol.DMTCS Proceedings vol. AJ,... (Proceedings), p.691-704
Main Author: Rubey, Martin
Format: Article
Language:English
Subjects:
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[math.math-co] mathematics [math]/combinatorics [math.co]
Combinatorics
Computer Science
Discrete Mathematics
Mathematics
nestings and crossings of matchings and permutations
pdsaws
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1365-8050
1462-7264
1365-8050
DOI:10.46298/dmtcs.3611