Tuesday, April 03, 2007

Generalized(?) Dyck Paths

A Dyck path is a useful metaphor for dealing with Catalan numbers. Suppose you are walking on an n X n grid, starting at (0,0). You can make a horizontal move to the right or a vertical move upwards. A Dyck path is a path in this grid where
  • the path ends at (n,n)
  • the path may touch (but never goes over) the main diagonal
The number of Dyck paths is precisely the Catalan number Cn-1. One way of seeing this is that all Dyck paths that touch the diagonal at some interior point can be written as the concatenation of two Dyck paths of shorter length (one from the origin to the point, and one from the point to (n,n)). Dyck paths are also related to counting binary trees, and strings of balanced parentheses (called Dyck languages).

People have studied "generalized" Dyck paths, where the grid is now rectangular (n X m), and the step lengths are appropriately skewed. However, what I'm interested in is the following seemingly simple generalization:
Let a (n,k)-Dyck path be a Dyck path with the modification that the path, instead of ending at (n,n), ends at (n,k) (k <=n). What is the number of (n,k)-Dyck paths ?
It seems like this should have been looked at, but I've been unable so far to find any reference to such a structure. I was wondering if readers had any pointers ? Note that this number is at most Cn-1 since any such path can be completed into a unique Dyck path.

3 comments:

  1. See http://www.research.att.com/~njas/sequences/A009766

    The formula you are looking for seems to be

    a(n, k)= binomial(n+k,n)*(n-k+1)/(n+1)

    In particular, a(n, n-1) = a(n, n), which is clear geometrically.

    ReplyDelete
  2. Hi

    I looked at an isomorphic catalan system all summer and they are totally awesome. Sleator Tarjan and Thruston tightly bounded the rotation distance of binary trees for a fixed n using hyperbolic geometry--we were tying to produce examples of triangulations that exhibit the diameter. We came up with a bunch of stuff but not quite what we were looking for.

    Do you know if anyone has looked Dyck paths as a type of path homotopy? Eg if you glue the lattice square to get the torus then a diagonal path wraps quotients into a loop.

    -m

    ReplyDelete
  3. Anon1: thanks for the tip - that's what we needed !

    Anon2: sounds fascinating. I don't know anything about it, but if you have a link I'd love to hear more.

    ReplyDelete

Disqus for The Geomblog