An involution on Dyck paths and its consequences (Q1300973): Difference between revisions

Dyck paths of semilength \(n\) are paths from \((0,0)\) to \((2n,0)\) with steps \(u=(1,1)\) and \(d=(1,-1)\) which lie on or above the \(x\)-axis. Many statistics of Dyck paths have been well studied, like the number of peaks (i.e. \(ud\)'s), the number of valleys (i.e. \(du\)'s), the number of doublerises (i.e. \(uu\)'s), the height of the first peak (i.e. the length of the initial run of \(u\)'s), and the number of returns (i.e. the number of \(d\)'s landing on the \(x\)-axis). It has been known that the number of doublerises and valleys have the same distribution among Dyck paths of semilength \(n\), and so do the height of the first peak and the number of returns. The present paper constructs an involution on the set of Dyck paths of semilength \(n\) which immediately proves both equidistribution theorems.