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

Miklós Bóna¹ ; Stoyan Dimitrov² ; Gilbert Labelle³ ; Yifei Li⁴ ; Joseph Pappe⁵ ; Andrés R. Vindas-Meléndez⁶ ; Yan Zhuang⁷

¹University of Florida
²Rutgers University
³Université du Québec à Montréal
⁴University of Illinois at Springfield
⁵Colorado State University
⁶MSRI
⁷Davidson College

The electronic journal of combinatorics, Tome 32 (2025) no. 2

Résumé

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},\ldots, k_{r}}$ counting the semilength-$n$ Dyck paths with $k_{1}$ $UD$-factors, $k_{2}$ $UUD$-factors, $\ldots$, 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.

Détail

DOI : 10.37236/12681

Classification : 05A15, 05A10, 05A19, 05C05, 05C30
Mots-clés : Dyck paths, lattice path