Number of Dyck paths with bounded height and fixed number of peaks

277 Views Asked by At

The number of Dyck paths of length $2n$ and exactly $k$ peaks is given by the Narayana numbers: \begin{equation} \frac{1}{n} {n\choose k}{n \choose k-1} \end{equation}

In a OEIS A080934, a recurrence relation is given for the number of Dyck paths with maximum height less than or equal to $h$, as well as a closed form solution. Looking at the same logic as in a previous question, it seems that the number of Dyck paths with halflength $n$, $k$ peaks and bounded in height by $h$ (call it $H(n,k,h)$) should obey the recursion relation \begin{equation} H(n+1,k,h) = \sum_{i=0}^n\sum_{j=0}^i H(i,j,h)H(n-i,k-j,h-1) \end{equation} With a few initial conditions such as $H(0,k,h) = \delta_{k0}$, $H(n,0,h) = \delta_{n0}$, $H(n,k,0) = \delta_{n0}\delta_{k0}$ . From this recursion relation, is it possible to derive a trivariate generating function $G(x,y,z) = \sum_{x,y,z}H(n,k,h)x^ny^kz^h$, or even a closed form solution for H (though that might be optimistic)?

Edit: I previously had the wrong bounds on the sum, we must include the possibility of the first return being the empty path

1

There are 1 best solutions below

2
On

Consider the bivariate generating function, where we keep $h$ fixed: $$ F_h(x,y)=\sum_{n,m\ge 0}H(n,k,h)x^ny^k $$ By decomposing a Dyck path with height at most $h$ into the times when it returns to the $x$ axis, we see that a path with height $h$ is an ordered sequence of paths with height $h-1$. If you sum (length + 1) over all sub-paths, you get the length of the whole path. If you sum the peaks of the sub-paths, you get the total number of peaks, with one exception; an empty path has zero peaks, but it contributes on peak to the total.

Translating all this to generating function language, $$ F_h(x,y)=\frac1{1-x(F_{h-1}(x,y)-1+y)} $$ Unfortunately, I do not see how to derive the trivariate generating function you mentioned. However, you can prove by induction that $F_h$ can be written in the form $$ F_h(x,y)=\frac{P_h(x,y)}{Q_h(x,y)} $$ for some polynomials $P_h,Q_h$.