×

Dyck paths with no peaks at height \(k\). (English) Zbl 0969.05002

Summary: 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 \(G_k(x)\) be the generating function for the number of Dyck paths of length \(2n\) with no peaks at height \(k\) with \(k\geq 1\). It is known that \(G_1(x)\) is the generating function for the Fine numbers (sequence A000957 in [N. J. A. Sloane, The on-line encyclopedia of integer sequences (published electronically)]). In this paper, we derive the recurrence \[ G_k(x) = \frac{1}{1-xG_{k-1}(x)}, \quad k \geq 2, \qquad G_1(x) = \frac{2} {1+2x+\sqrt{1-4x}}. \] It is interesting to see that in the case \(k=2\) we get \(G_2(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 \geq 0\), with no peaks at height 2 is the Catalan number \(c_n =\frac{1}{n+1}\binom{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\).

MSC:

05A15 Exact enumeration problems, generating functions

Software:

OEIS
PDFBibTeX XMLCite
Full Text: EuDML EMIS