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?

  • 0
    Have you tried calculating a few, and then consulting the Online Encyclopedia of Integer Sequences?2012-09-04
  • 0
    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.2012-09-04
  • 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.

  • 2
    See also [OEIS sequence A080934](http://oeis.org/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.)2012-09-04
  • 0
    Thanks very much, both of you! This is exactly what I needed.2012-09-04
  • 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