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


1 Answer 1


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

  • $\begingroup$ Please see equation (10) on pg. 53 of arxiv.org/pdf/1409.2562.pdf. $\endgroup$ Oct 16, 2021 at 17:35
  • $\begingroup$ 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. $\endgroup$ Oct 16, 2021 at 18:57
  • $\begingroup$ @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. $\endgroup$ Oct 16, 2021 at 19:29
  • 1
    $\begingroup$ Now, it is great! $\endgroup$ Oct 16, 2021 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.