# Enumeration of dominated Dyck paths

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)=?$$

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:

• Please see equation (10) on pg. 53 of arxiv.org/pdf/1409.2562.pdf. Oct 16, 2021 at 17:35
• I noticed there is something wrong about this equation (10). The right-hand side give many fractional values while the left-hand side is clearly of integers. Oct 16, 2021 at 18:57
• @T.Amdeberhan: yes, there's a typo there in that the indices in the product should be $i\leq j$. See my edit for the formula in your case. Oct 16, 2021 at 19:29
• Now, it is great! Oct 16, 2021 at 20:19