4
$\begingroup$

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?

  • 1
    A Mathematica program related to Dyck paths and Catalan numbers: http://pastebin.com/fsCtBUe12013-11-24

1 Answers 1

6

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.

  • 0
    And here is a link to the paper by Ilić and Ilić that demonstrates that there is no closed-form answer to my question. http://operator.pmf.ni.ac.rs/www/pmf/publikacije/filomat/2011/F25-3-2011/F25-3-17.pdf2012-09-04