Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
A Mathematica program related to Dyck paths and Catalan numbers: pastebin.com/fsCtBUe1 –  Mats Granvik Nov 24 '13 at 8:20
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
2  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.