solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看304次
A bijection between bargraphs and Dyck paths. (arXiv:1705.05984v1 [math.CO])
来源于:arXiv
Bargraphs are a special class of convex polyominoes. They can be identified
with lattice paths with unit steps north, east, and south that start at the
origin, end on the $x$-axis, and stay strictly above the $x$-axis everywhere
except at the endpoints. Bargraphs, which are used to represent histograms and
to model polymers in statistical physics, have been enumerated in the
literature by semiperimeter and by several other statistics, using different
methods such as the wasp-waist decomposition of Bousquet-M\'elou and
Rechnitzer, and a bijection with certain Motzkin paths.
In this paper we describe an unusual bijection between bargraphs and Dyck
paths, and study how some statistics are mapped by the bijection. As a
consequence, we obtain a new interpretation of Catalan numbers, as counting
bargraphs where the semiperimeter minus the number of peaks is fixed. 查看全文>>