5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Check out math.upenn.edu/~wilf/gfologyLinked2.pdf for Part 2 of your post. $\endgroup$ – Moritz Dec 27 '18 at 15:18
  • 1
    $\begingroup$ This is exactly the range where, if the path returns to 0, only one trip away from 0 can have height k. Maybe that's relevant. $\endgroup$ – Will Sawin Dec 27 '18 at 21:13
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The reflection principle can be used to find the general formula for Dyck paths of height at most $k$ with no restriction on $k$ referred to in my answer below with the group of reflections isomorphic to the infinite dihedral group. This was first done by Howard D. Grossman, Fun with lattice points, Scripta Math. 15 (1949), 79–81. $\endgroup$ – Ira Gessel Dec 29 '18 at 1:35
  • $\begingroup$ Thanks! I'll add the reference to make it clear I'm not the first to notice this trick, but can't find this paper anywhere. Do you have it? $\endgroup$ – Puck Rombach Dec 29 '18 at 7:58
  • $\begingroup$ I used to have a copy somewhere in my office, but I'm not sure that I can find it. You might try getting it by interlibrary loan if you really want it. The reflection proof can also be found in Krattenthaler's paper referenced below Theorem 10.18.6 in a much more general form. $\endgroup$ – Ira Gessel Dec 29 '18 at 22:47
  • $\begingroup$ I'm fine: I was thinking more in terms of being useful to the questioner (and other readers). $\endgroup$ – Puck Rombach Dec 29 '18 at 23:12
  • $\begingroup$ @PuckRombach, Is it also true for $1\leq k\leq n$ $\endgroup$ – 1Spectre1 Dec 30 '18 at 6:53
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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