A combinatorial proof of a symmetry for a refinement of the Narayana numbers

Abstract

We establish a tantalizing symmetry of certain numbers refining the Narayana numbers. In terms of Dyck paths, this symmetry is interpreted in the following way: if $w_{n,k,m}$ is the number of Dyck paths of semilength $n$ with $k$ occurrences of $UD$ and $m$ occurrences of $UUD$, then $w_{2k+1,k,m}=w_{2k+1,k,k+1-m}$. We give a combinatorial proof of this fact, relying on the cycle lemma, and showing that the numbers $w_{2k+1,k,m}$ are multiples of the Narayana numbers. We prove a more general fact establishing a relationship between the numbers $w_{n,k,m}$ and a family of generalized Narayana numbers due to Callan. A closed-form expression for the even more general numbers $w_{n,k_1,k_2,\dots ,k_r}$ counting the semilength-$n$ Dyck paths with $k_1$ $UD$-factors, $k_2$ $UUD$-factors, $\dots$ , and $k_r$ $U^{r}D$-factors is also obtained, as well as a more general form of the discussed symmetry for these numbers in the case when all rise runs are of certain minimal length. Finally, we investigate properties of the polynomials $W_{n,k}(t)={\sum }_{m=0}^k{w}_{n,k,m}{t}^m$, including real-rootedness, $\gamma$-positivity, and a symmetric decomposition.

23 pages, 1 table, 2 figures. Updated version; previously titled, "A combinatorial proof of a tantalizing symmetry on Catalan objects." To appear in Electronic Journal of Combinatorics