Enumeration of chains and saturated chains in Dyck lattices

NEW

Problem: The literal displayed formula in the prompt is missing the asymptotic symbol: read literally it would say $i_h=(i_h)n^h/2^h$, which is false, e.g. $h=1,n=3$. The paper’s definition of “asymptotically Boolean” supports the intended conjecture:

For every fixed integer $h\ge1$, in the Dyck lattice $\mathcal D_n$ of Dyck paths of semilength $n$, ordered by containment,

where $sc_h$ counts saturated chains with $h$ cover steps.

Result: The conjecture is true.

A cover in $\mathcal D_n$ is exactly the replacement of a valley $du$ by a peak $ud$. For a Dyck path $\gamma$, let $v(\gamma)$ be its number of valleys, and let $f_h(\gamma)$ be the number of saturated chains of length $h$ starting at $\gamma$. Then

If $\tau\gamma$ is obtained by changing one valley $du$ to $ud$, then only the three adjacent pairs around that valley can change, hence

We prove by induction on fixed $h$ that, uniformly in $\gamma\in D_n$,

For $h=1$, this is exact. If true for $h$, then

because there are $v(\gamma)\le n$ possible covers and each changes $v$ by at most $1$.

Thus

where $\Gamma_n$ is a uniform random Dyck path of semilength $n$.

Let $K_n$ be the number of peaks. Since Dyck paths start with $u$ and end with $d$,

By the Narayana distribution,

Vandermonde’s identity gives

Hence

in $L^2$, and therefore, for every fixed $h$,

So

Since $(n)_h\sim n^h$, the Hasse index is asymptotically Boolean.

Audit: $h$ is fixed while $n\to\infty$; the cover relation used is the standard Dyck-lattice cover; no extra hypotheses are introduced; the conclusion is exactly $i_h(\mathcal D_n)\sim n^h/2^h$.

Citation: Ferrari–Munarini, “Enumeration of saturated chains in Dyck lattices,” Adv. Appl. Math. 62 (2015), 118–140, for the conjecture and definitions. The Narayana peak distribution is classical.