Nestings of matchings and permutations and north steps in PDSAWs

M Rubey - Discrete Mathematics & Theoretical Computer …, 2008 - dmtcs.episciences.org
Discrete Mathematics & Theoretical Computer Science, 2008dmtcs.episciences.org
We present a simple bijective proof of the fact that matchings of 2n with N nestings are
equinumerous to partiallydirectedselfavoidingwalks 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.
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.
dmtcs.episciences.org
以上显示的是最相近的搜索结果。 查看全部搜索结果