A bijection between 2-triangulations and pairs of non-crossing Dyck paths
A bijection between 2-triangulations and pairs of non-crossing Dyck paths
复制标题
2-三角剖分和成对非交叉 Dyck 路径之间的双射
DOI：
10.1016/j.jcta.2007.03.002
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Sergi Elizalde
中科院分区：
文献类型：
--
作者：
Sergi Elizalde
凸多边形的k-三角剖分是对角线的最大集合，使得没有k+1个对角线在其内部相互交叉。我们给出了一个凸n边形的2三角剖分与长度为2(n−4)的不相交Dyck路对之间的双射。这解决了在k=2的情况下寻找Jonsson结果的双射证明的问题。我们通过构造2-三角剖分集和不相交的Dyck路对的同构生成树来获得双射。
A k-triangulation of a convex polygon is a maximal set of diagonals so that no k+1 of them mutually cross in their interiors. We present a bijection between 2-triangulations of a convex n-gon and pairs of non-crossing Dyck paths of length 2(n−4). This solves the problem of finding a bijective proof of a result of Jonsson for the case k=2. We obtain the bijection by constructing isomorphic generating trees for the sets of 2-triangulations and pairs of non-crossing Dyck paths.