A bijection on Dyck paths and its consequences
type: Item
instance of: scholarly article
title: A bijection on Dyck paths and its consequences
zbMATH Open document ID: 0890.05005
DOI: 10.1016/S0012-365X(97)00097-6
author: Emeric Deutsch
published in: Discrete Mathematics
publication date: 1998-06-29T00:00:00Z
review text: A Dyck path of semilength \(n\) is a path in the first quadrant beginning at \((0,0)\), ending at \((2n,0)\), and consisting of rises (steps of \((1,1)\)) and falls (steps of \((1,-1)\)). This article gives several proofs, one of which uses a bijection, of the fact that there are as many Dyck paths of semilength \(n\) beginning with exactly \(k\) consecutive rises (height of the first peak equals \(k\)) as there are with exactly \(k\) falls landing on the horizontal axis (\(k\) returns). As a consequence of the bijection it is shown that the Narayana numbers \(u(n,k)= \left({1\over n}\right) \left(\begin{smallmatrix} n\\ k\end{smallmatrix}\right) \left(\begin{smallmatrix} n\\ k+1\end{smallmatrix}\right)\) (*), which count Dyck paths of semilength \(n\) with \(k\) valleys (falls followed by rises) also count Dyck paths of semilength \(n\) with \(k\) high peaks (rises to a height of at least 2 followed by falls). (*) Reviewer's remark: It would have been helpful if the article had stated which of the references contains this result and had included the figure to which it refers.
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 1109999
zbMATH Keywords: Dyck path
zbMATH Keywords: returns
zbMATH Keywords: Narayana numbers
zbMATH Keywords: high peaks
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
cites work: Q5538132
cites work: Q4320535
cites work: Q3752390
cites work: A new enumerative property of the Narayana numbers
cites work: Subdivision des nombres de Narayana suivant deux paramètres supplémentaires. (Subdivision of Narayana numbers following two supplementary parameters)
cites work: Catalan path statistics having the Narayana distribution
cites work: Six etudes in generating functions
full work available at URL: s0012-365x(97)00097-6
OpenAlex ID: W1977176424
description: scientific article; zbMATH DE number 1109999