Portal de Periódicos da CAPES

Enumerating several aspects of non-decreasing Dyck paths

2019; Elsevier BV; Volume: 342; Issue: 11 Linguagem: Inglês

10.1016/j.disc.2019.06.018

1872-681X

Rigoberto Flórez, Leandro Junes, Jósé L. Ramírez,

Advanced Mathematical Identities

A Dyck path is non-decreasing if the y-coordinates of its valleys form a non-decreasing sequence. In this paper we give enumerative results and some statistics of several aspects of non-decreasing Dyck paths. We give the number of pyramids at a fixed level that the paths of a given length have, count the number of primitive paths, count how many of the non-primitive paths can be expressed as a product of primitive paths, and count the number of paths of a given height and a given length. We present and prove our results using combinatorial arguments, generating functions (using the symbolic method) and parameterize the results studied here using the Riordan arrays. We use known bijections to connect direct column-convex polyominoes, Elena trees, and non-decreasing Dyck paths.