Dyck Paths With No Peaks At Height k-猫眼课题宝

DOI：

发表时间：

2001-05

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Paul Peart;Wen-Jin Woan

长度为2n的戴克路径是一条从（0，0）到（2n，0）的双空间路径，它只使用（1，1）（东北）和（1，−1）（东南）的步长。此外，Dyck路径不低于x轴。戴克路径上的峰是一个节点，紧接着是东北阶，紧接着是东南阶。如果峰的y坐标为k，则峰位于高度k处。设Gk（x）是长度为2n且在高度k处没有峰的Dyck路径的数目的生成函数，其中k ≥ 1。已知G1（x）是Fine数的生成函数（[6]中的序列A000957）。本文给出了递推式Gk（x）= 1 1− xGk−1（x），k ≥ 2，G1（x）= 2 1 + 2x+<$1 − 4x .有趣的是，在k = 2的情况下，我们得到G2（x）= 1+xC（x），其中C（x）是无处不在的加泰罗尼亚数（A000108）的生成函数。这意味着长度为2n + 2，n ≥ 0，在高度为2处没有峰的戴克路的数目是卡塔兰数cn = 1 n+1（2n n）。我们还提供了一个组合的证明，这最后一个事实，通过引入一个双射之间的所有戴克路径的长度为2n+ 2，没有峰的高度为2和所有戴克路径的长度为2n。

A Dyck path of length 2n is a path in two-space from (0, 0) to (2n, 0) which uses only steps (1, 1) (north-east) and (1,−1) (south-east). Further, a Dyck path does not go below the x-axis. A peak on a Dyck path is a node that is immediately preceded by a north-east step and immediately followed by a south-east step. A peak is at height k if its y-coordinate is k. Let Gk(x) be the generating function for the number of Dyck paths of length 2n with no peaks at height k with k ≥ 1. It is known that G1(x) is the generating function for the Fine numbers (sequence A000957 in [6]). In this paper, we derive the recurrence Gk(x) = 1 1− xGk−1(x) , k ≥ 2, G1(x) = 2 1 + 2x+ √ 1− 4x . It is interesting to see that in the case k = 2 we get G2(x) = 1+xC(x), where C(x) is the generating function for the ubiquitous Catalan numbers (A000108). This means that the number of Dyck paths of length 2n + 2, n ≥ 0, with no peaks at height 2 is the Catalan number cn = 1 n+1 ( 2n n ) . We also provide a combinatorial proof for this last fact by introducing a bijection between the set of all Dyck paths of length 2n+ 2 with no peaks at height 2 and the set of all Dyck paths of length 2n.

Dyck Paths With No Peaks At Height k

文献摘要

被引文献

相似文献