![]() |
Discrete Mathematics & Theoretical Computer Science |
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.
Source : ScholeXplorer
IsRelatedTo DOI 10.1016/0012-365x(80)90050-3 Source : ScholeXplorer IsRelatedTo DOI 10.1016/0012-365x(80)90248-4 Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.disc.2006.03.020
|