The number of Dyck paths of length $2n$ and height exactly $k$

Question

In A080936 gives the number of Dyck paths of length $2n$ and height exactly $k$ and has a little more information on the generating functions.

For all $n\geq 1$ and $\frac{(n+1)}{2}\leq k\leq n$ we have: $$T(n,k) = \frac{2(2k+3)(2k^2+6k+1-3n)(2n)!}{((n-k)!(n+k+3)!)}.$$

• I couldn't find any proof for the above equality and any source (article, book, (etc,.)?

• I need to understand how to construct generating functions and formulas The number of Dyck paths of length $2n$ and height exactly $k$.

Answer 1

EDIT: Ira points out that the below method, for general $k$, appears in Howard D. Grossman, Fun with lattice points, Scripta Math. 15 (1949), 79–81, but this paper does not seem to be available online. The more general version of this question (lattice paths between two points that stay inside some chamber) is in this Krattenthaler paper (https://arxiv.org/abs/1503.05930).

We can prove this along the lines of the reflection method used for the standard Catalan numbers. (Read about this first if you have never seen it.)

There are $\binom{2n}{n}$ paths from the lower hand corner (0,0) to the upper right hand corner (n,n) of the square.

For the paths that move above the diagonal, we reflect after the first point above the diagonal (a), over the line through (a) and (n,n), to find a bijection between paths that move above the diagonal and paths from (0,0) to (n-1,n+1).

This gives us the usual Catalan numbers: $$C_n=\binom{2n}{n}-\binom{2n}{n-1}.$$

We can count paths that cross the line through (k,0) and $(n,k)$ in the same manner. We have $$\binom{2n}{n-k-1}$$ such paths.

This will help us find the paths of height at most $k$, but we can't simply subtract this number from the Catalan numbers, because we must take into account paths that cross both lines. This can happen in 3 ways (when $\frac{n-1}{2} \leq k \leq n$). Will Sawin's comment was useful here, as he noted that we cannot return to 0 after reaching height $k$.

• A path can cross the diagonal and then cross the $k$-line. Using a double-reflection bijection we see that there are $$\binom{2n}{n-k-2}$$ such paths.

• A path can cross the $k$-line and then the diagonal. Using a double-reflection bijection we see that there are $$\binom{2n}{n-k-2}$$ such paths.

• The above two sets of paths intersect at the third option: our path crosses the diagonal, then the $k$-line, and then the diagonal again. We do a triple-reflection bijection to see that there are $$\binom{2n}{n-k-3}$$ such paths.

Putting all of this together, we find the number of Dijck paths of height at most $k$, $\frac{n-1}{2} \leq k \leq n$, as $$S(n,k)=\binom{2n}{n}-\binom{2n}{n{-}1}-\binom{2n}{n{-}k{-}1}+2\binom{2n}{n{-}k{-}2}-\binom{2n}{n{-}k{-}3}.$$

Therefore, the number of paths of height exactly $k$, when $\frac{n+1}{2} \leq k \leq n$, is $$T(n,k)=S(n,k)-S(n,k{-}1)=\binom{2n}{n{-}k}-3\binom{2n}{n{-}k{-}1}+3\binom{2n}{n{-}k{-}2}-\binom{2n}{n{-}k{-}3}.$$

(I used Wolfram to verify that this is indeed the $T(n,k)$ that you mention.)

MORE EDIT: Let's write out the formula for general $k$ here for completeness. Note that this is still all a special case of Theorem 10.3.3 and Theorem 10.18.6 in Krattenthaler (https://arxiv.org/abs/1503.05930).

For general $k$, we should assume that the line can cross the diagonal and the $k$-line arbitrarily many times. If $A$ is the event that we cross the diagonal (some number of times without crossing the $k$-line), and $B$ is the event that we cross the $k$-line (some number of times without crossing the diagonal), then our possible paths look like $0,A,B,AB,BA,ABA,BAB,ABAB,BABA,...$ (a set that is isomorphic to the infitine dihedral group). Note that for some given finite $k$ and $n$, there is a limit on how many times we can cross, so even though we'll write down infinite sum, only finitely many terms will be nonzero.

We generalize the inclusion-exclusion type counting argument we were using before, to see that (using terrible notation):

|good paths| = |total paths| - |$\geq 1$ crossings| + |$\geq 2$ crossings| - |$\geq 3$ crossings| +...

If we let $AB^*$ denote the paths that start with event $AB$, etc, we get

|good paths|= $|^*|$-$|A^*|$-$|B^*|$+$|AB^*|$+$|BA^*|$-$|ABA^*|$-$|BAB^*|$+...

If a term in this expression has $i$ $A$s and $j$ $B$s, we generalize the multiple-reflection method from before to see that the number of such paths is $$\binom{2n}{n-i-j(k+1)}.$$ And $i$ and $j$ differ by at most one, because our events $A$ and $B$ always alternate. With some messing around, we can now write this as a single, infinite sum:

$$S(n,k)=\sum_{j \in \mathbb{Z}_{\geq 0}} \left( \binom{2n}{n-\left\lfloor \frac{j+1}{2} \right\rfloor (k+2)} -\binom{2n}{n- f(j)} \right)$$

where

$$f(j)=\begin{cases} \frac{j}{2} (k+2)+1, \;\; j\equiv 0 \pmod{2},\\ \frac{j+1}{2}(k+2)-1, \;\; j\equiv 1 \pmod{2}. \end{cases}$$

This is Krattenthaler 10.3.3 when $a=b=t=0,\; c=d=n,\; s=-k$. Now, we have (and sorry for reusing the labels $S(n,k)$ and $T(n,k)$), for general $n$ and $k$,

$$T(n,k)=S(n,k)-S(n,k-1).$$

Answer 2

This is really a comment, but it's a little too long.

There is a well-known formula for the generating function for Dyck paths of height at most $k$ as a quotient of polynomials closely related to Chebyshev polynomials. So to get Dyck paths of height exactly $k$ you need to take the difference of two of these generating functions; there really isn't any simplification. The formula for these rational generating functions can be found, for example, in https://cs.uwaterloo.ca/journals/JIS/VOL8/Gessel/xin.pdf, pp. 10–11.

For the formula for the special case $(n+1)/2\le k\le n$, my guess is that it comes from the formula for counting Dyck paths of bounded height as an alternating sum of binomial coefficients; see https://arxiv.org/abs/1503.05930, Theorem 10.3.3. I did not try to work out the details.