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?

$\endgroup$
3
  • $\begingroup$ Have you tried calculating a few, and then consulting the Online Encyclopedia of Integer Sequences? $\endgroup$ Sep 4, 2012 at 2:20
  • $\begingroup$ 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. $\endgroup$
    – Michael K
    Sep 4, 2012 at 4:25
  • 1
    $\begingroup$ A Mathematica program related to Dyck paths and Catalan numbers: pastebin.com/fsCtBUe1 $\endgroup$ Nov 24, 2013 at 8:20

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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.) $\endgroup$
    – joriki
    Sep 4, 2012 at 3:47
  • $\begingroup$ Thanks very much, both of you! This is exactly what I needed. $\endgroup$
    – Michael K
    Sep 4, 2012 at 15:29
  • $\begingroup$ 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/… $\endgroup$
    – Michael K
    Sep 4, 2012 at 16:16

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .