Skip to main content
5 of 9
deleted 15 characters in body

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.

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.

enter image description here

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).

enter image description hereenter image description here

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.

enter image description hereenter image description here

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.

enter image description hereenter image description here

  • 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.

enter image description hereenter image description here

  • 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.

enter image description hereenter image description here

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.)