Some Connections Between Restricted Dyck Paths, Polyominoes, and Non-Crossing Partitions

A Dyck path is a lattice path in the first quadrant of the xy-plane that starts at the origin, ends on the x-axis, and consists of the same number of North-East steps U and South-East steps D. A valley is a subpath of the form DU. A Dyck path is called restricted d-Dyck if the difference between any two consecutive valleys is at least d (right-hand side minus left-hand side) or if it has at most one valley. In this paper we give some connections between restricted d-Dyck paths and both, the non-crossing partitions of [n] and some subfamilies of polyominoes. We also give generating functions to count several aspects of these combinatorial objects.