Skip to main content
9 of 9
added 358 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. 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.

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

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