# Dyck Paths, Catalan Numbers, and Trapezoidal Parallelogram Polyominoes

I've been trying to find the number of Dyck paths $P$ of length $2n$ such that $\forall (x,y) \in P, |x-y| \le k$ for some fixed constant $k$. These are the Dyck paths that are bounded by the lines $y=x$, $y=x-k$, $y=0$, and $x=n$. This is also the number of trapezoidal parallelogram polyominoes.

If we let $P(n,k)$ be the number of paths, it is easy to prove that $C_n \ge P(n,k) \ge (C_k)^{n/k}$, where the first equality is tight if $n\le k$ and the final equality is tight only for $k=1$.

This question may be too general, but does anyone know of a closed form for the function $P(n,k)$? Or at least have a clue about how to continue towards one?

-
Have you tried calculating a few, and then consulting the Online Encyclopedia of Integer Sequences? – Gerry Myerson Sep 4 '12 at 2:20
I have, unfortunately the space of possible choices of $(n,k)$ gets large very fast, and it's hard to tell which pair will be the most informational. – Michael K Sep 4 '12 at 4:25
A Mathematica program related to Dyck paths and Catalan numbers: pastebin.com/fsCtBUe1 – Mats Granvik Nov 24 '13 at 8:20

## 1 Answer

Counting Dyck paths can be rephrased as the problem of counting walks on the semi-infinite path graph $\mathbb{Z}_{\ge 0}$ from the origin $0$ to itself. Counting these restricted paths is equivalent to the problem of counting walks on this graph which do not stray more than $k$ from the origin, which is equivalent to the problem of counting walks on a finite path graph of length $k$ from one end to itself.

For fixed $k$ this sequence is described by a linear recurrence, or equivalently it has rational generating function. These generating functions are written down somewhat explicitly in this blog post: they appear as convergents of a continued fraction

$$\frac{1}{1 - \frac{x}{1 - \frac{x}{1 - ...}}}$$

describing the generating function of the Catalan numbers.

-
See also OEIS sequence A080934 and the generating functions given and papers referenced there. (Note that there seem to be some minor errors; $k$ and $n$ seem to be swapped in the second entry under "comments", and the paper by Ilić and Ilić seems to use "touch" sometimes when "cross" is intended.) – joriki Sep 4 '12 at 3:47
Thanks very much, both of you! This is exactly what I needed. – Michael K Sep 4 '12 at 15:29
And here is a link to the paper by Ilić and Ilić that demonstrates that there is no closed-form answer to my question. operator.pmf.ni.ac.rs/www/pmf/publikacije/filomat/2011/… – Michael K Sep 4 '12 at 16:16