Counting peaks at height k in a Dyck path
Counting peaks at height k in a Dyck path
复制标题
DOI：
--
复制
发表时间：
2002-03
期刊：
影响因子：
--
通讯作者：
T. Mansour
中科院分区：
文献类型：
--
作者：
T. Mansour
Dyck路径是平面整数格$\mathbb{Z}\times\mathbb{Z}$中的格路径，由步骤（1，1）和（1，-1）组成，它从不通过x轴以下。在Dyck路径上高度为k处的峰是具有坐标y=k的路径上的点，其紧接在（1，1）阶跃之前并且紧接在（1，-1）阶跃之后。在本文中，我们找到了一个显式的生成函数的Dyck路径的数量开始于（0，0）和结束于（2n，0），正好r个峰的高度为k。这允许我们通过第二类切比雪夫多项式和加泰罗尼亚数的生成函数来表达这个函数。
A Dyck path is a lattice path in the plane integer lattice $\mathbb{Z}\times\mathbb{Z}$ consisting of steps (1,1) and (1,-1), which never passes below the x-axis. A peak at height k on a Dyck path is a point on the path with coordinate y=k that is immediately preceded by a (1,1) step and immediately followed by a (1,-1) step. In this paper we find an explicit expression to the generating function for the number of Dyck paths starting at (0,0) and ending at (2n,0) with exactly r peaks at height k. This allows us to express this function via Chebyshev polynomials of the second kind and generating function for the Catalan numbers.