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

Miklós Bóna, S. I. Dimitrov, Gilbert Labelle, Yifei Li, Joseph Pappe, Andrés R. Vindas-Meléndez, Yan Zhuang

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}, \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.

Introduction

In enumerative combinatorics, Dyck paths are fundamental objects: lattice paths that start and end on the x-axis, consisting of up steps ($U$) and down steps ($D$), never dipping below the axis. The total number of Dyck paths of a certain semilength $n$ is given by the famous Catalan numbers.

A classic refinement is the Narayana number $N_{n,k}$, which counts Dyck paths of semilength $n$ with exactly $k$ "peaks" (the pattern $UD$). While Narayana numbers themselves exhibit a well-known symmetry ($N_{n,k} = N_{n, n+1-k}$), this research investigates a deeper refinement: $w_{n,k,m}$, which counts paths with $k$ peaks ($UD$) and $m$ occurrences of a longer "rise" pattern ($UUD$).

The Tantalizing Symmetry

Previously, an algebraic proof existed for a specific symmetry: $w_{2k+1,k,m} = w_{2k+1,k,k+1-m}$. However, a purely combinatorial explanation—one that explains why this happens through structural mapping rather than just symbol manipulation—had remained elusive. This paper provides the first such combinatorial proof.

Figure 1: Illustration of the symmetry $w_{5,2,1} = w_{5,2,2} = 5$. Row (A) shows the five Dyck paths of semilength 5 with 2 peaks and 1 occurrence of UUD. Row (B) shows the five paths with 2 peaks and 2 occurrences of UUD.

As illustrated in Figure 1, at the specific semilength $n = 2k+1$, the distribution of $UUD$ factors is perfectly symmetric. The paper reveals a striking scaling property: $w_{2k+1,k,m} = \binom{2k+1}{k-1} N_{k,m}$. This identity shows that these refined counts are essentially the Narayana numbers "inflated" by a binomial coefficient, providing a direct link between the two sequences.

Methodology

The authors employ several sophisticated combinatorial tools to bridge the gap between algebraic formulas and structural understanding:

  • The Cycle Lemma (Raney's Lemma): This is the core engine of the proof. It allows the authors to take a sequence of steps that might go below the x-axis and determine exactly how many cyclic shifts of that sequence result in a valid, non-negative Dyck path.
  • Extended Peaks and Necklaces: The authors define an "extended peak" as a sequence of $U$s followed by a single $D$. By arranging these into "necklaces" (equivalence classes under cyclic rotation), they use the Cycle Lemma to count how many valid Dyck paths can be formed from a given set of rises.
  • Bijective Mappings: They construct explicit bijections between these necklaces and Dyck paths, effectively proving the relationship between $w_{2k+1,k,m}$ and the Narayana numbers $N_{k,m}$.

Key Results and Generalizations

Beyond the primary symmetry, the research offers several broader contributions:

  1. Generalization to $U^rD$: The authors extend their logic beyond $UUD$ patterns. They provide a general closed-form expression for $w_{n,k_1, k_2, \dots, k_r}$, which counts occurrences of $UD, UUD, \dots, U^rD$. This suggests the observed symmetry is part of a much larger family of combinatorial identities.
  2. Polynomial Geometry: By proving the generating polynomials $W_{n,k}(t) = \sum w_{n,k,m} t^m$ are real-rooted, the authors guarantee that the sequence of counts is unimodal (it has only one peak).
  3. $\gamma$-Positivity: The proof of $\gamma$-positivity for the symmetric cases ($n=2k \pm 1$) implies a deep internal symmetry in the structure of these polynomials, allowing them to be expanded in a specific gamma basis with non-negative coefficients.

Limitations and Future Work

While the paper provides a symmetric decomposition for $W_{n,k}(t)$ when it isn't naturally symmetric, the combinatorial interpretation of the parts of this decomposition remains a conjecture. Additionally, the authors suggest that the $\gamma$-coefficients they found might be related to Motzkin paths, but a formal combinatorial proof of this connection is left for future research. Finally, they conjecture that the sequences of these polynomials form "Sturm sequences," which would imply even stronger structural regularity in their roots.

Summary updated

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},\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, $γ$-positivity, and a symmetric decomposition.
BibTeX
@article{bona2025combinatorial,
  author = {Miklós Bóna and S. I. Dimitrov and Gilbert Labelle and Yifei Li and Joseph Pappe and Andrés R. Vindas-Meléndez and Yan Zhuang},
  title = {{A combinatorial proof of a symmetry for a refinement of the Narayana numbers}},
  journal = {The Electronic Journal of Combinatorics},
  year = {2025},
  doi = {10.37236/12681},
}
Figure