Nestings of Matchings and Permutations and North Steps in PDSAWs
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 permutations with $N$ …