Ascending runs in permutations and valued Dyck paths

Abstract

We define a bijection between permutations and valued Dyck paths, namely, Dyck paths whose odd vertices are labelled with an integer that does not exceed their height. This map allows us to characterize the set of permutations avoiding the pattern 132 as the preimage of the set of Dyck paths with minimal labeling. Moreover, exploiting this bijection we associate to the set of n-permutations a polynomial that generalizes at the same time Eulerian polynomials, Motzkin numbers, super-Catalan numbers, little Schröder numbers, and other combinatorial sequences. Lastly, we determine the Hankel transform of the sequence of such polynomials.