Enumeration of Dominated Dyck Paths – Analysis

co.combinatoricsenumerative-combinatoricsnt.number-theoryreference-request

Using horizontal steps $(1,0)$ and vertical steps $(0,-1)$, consider the lattice paths starting from $(0,q)$ and reaching $(p,0)$ with $p$ horizontal and $q$ vertical steps. The set of such paths $\frak{C}_{p,q}$ has cardinality $\binom{p+q}p$, which is ordered by
"dominance": a path $\pi$ dominates $\pi'$ if $\pi'$ lies entirely "weakly" between $\pi$ and the coordinate axes. Letting $w(\pi)$ be the number of paths dominated by $\pi$, Krewaras–Niederhausen show in Solution of an Enumerative Problem Connected with Lattice Paths the following enumeration (these form a triangle for Narayana numbers)
$$\sum_{\pi\in\frak{C}_{p,q}}w(\pi)=\frac{(p+q)!(p+q+1)!}{p!q!(p+1)!(q+1)!}.$$

Let's look at Dyck paths: staircase walks from $(0,0)$ to $(n,n)$ that lie "weakly" below the diagonal $y=x$. The number of such Dyck paths $\mathcal{C}_n$, of order $n$, is given by the Catalan number $C_n=\frac1{n+1}\binom{2n}n$.

Given $\pi\in\mathcal{C}_n$, let $w(\pi)$ be the number of Dyck paths $\pi'\in\mathcal{C}_n$ that lie "weakly" above $\pi$. Now, in a similar vain, I like to ask:

QUESTION. Is there anything known about the enumeration
$$\sum_{\pi\in\mathcal{C}_n}w(\pi)=?$$

Best Answer

In fact the result you attribute to Kreweras-Niederhausen is equivalent via a simple reformulation to counting plane partitions in a $p\times q \times 2$ box, i.e., plane partitions of $p\times q$ shape with entries in $\{0,1,2\}$, and hence follows from MacMahon's famous formula (which applies to rectangular plane partitions with entries in $\{0,1,\ldots,m\}$ for any $m$).

(What Kreweras-Niederhausen actually prove that is new in that paper is an analogous product formula for the order polynomial of the poset $V \times [n]$.)

Similarly, your question about Dyck paths amounts to counting plane partitions of staircase shape with entries in $\{0,1,2\}$. These plane partitions (for entries $\{0,1,\ldots,m\}$ for any $m$) were enumerated by Proctor: see, e.g., his "Odd symplectic groups" paper (https://doi.org/10.1007/BF01404455).

EDIT: For another explanation, see the discussion of fans of Dyck paths on pg. 53-54 of Ardila, "Algebraic and geometric methods in enumerative combinatorics," https://arxiv.org/abs/1409.2562.

EDIT: The specific formula in your case is: $$ \prod_{1 \leq i \leq j \leq n-1} \frac{i+j+4}{i+j}.$$ Compare to the number of Dyck paths $(0,0)\to(n,n)$ being $$ \prod_{1\leq i \leq j \leq n-1} \frac{i+j+2}{i+j}.$$ See my explanation in picture form: enter image description here

Related Question