Catalan Numbers and beyond!?

Question

First off, let me warn you that this comes from my messing around with the Catalan numbers.  It's, as far as I know, not a textbook problem, so there may not be a solution.  Point being this: I appreciate any input, but don't spend too much time if you start pulling out your hair.

On the other hand, it could be a very simple problem and I'm just have a brain fart, which could always happen.

----------

As you might already know, the Catalan numbers
1/(n+1) * [ (2n) choose n ]
count a lot of things.  For instance, they count the number of monotonic lattice paths on an n by n grid of squares such that the path doesn't go above the diagonal.

See, for instance:
https://en.wikipedia.org/wiki/Catalan_number

I want to throw a curve ball at this situation.  I want to add a rectangle to the right side of this n x n square so that we end up with a n x k rectangle.  Then we count the number of monotonic lattice paths on this n x k rectangle which doesn't go above the diagonal of the ORIGINAL square.

There's a way to count this recursively by looking at how high the path is when it finally reaches the right side of the square, but this recursive solution doesn't actually help me.

So the question: Is there a closed form (it can involve a finite sum, but nothing recursively defined) which counts this?

Thanks!

Nick · Accepted Answer

The Catalan numbers C(2n,n)/(n+1) count monotonic lattice paths that begin at (0,0), terminate at coordinate (n,n) and don't exceed the diagonal. They are the boundary case of the numbers

(m-n+1)*C(n+m+1,n)/(n+m+1) <----

which count monotonic lattice paths that *do not exceed the diagonal* and go from (0,0) to (m,n) m>=n.
These will give the number of said paths to *any* point below or on the diagonal itself. I think this includes inside and on the edges of your rectangle (if I understand you correctly - I'm not sure about this). Anyhow the above formula is surely more helpful that the Catalan numbers which are just a special "boundary case" of these.

-------------------------------------
The derivation of these numbers goes something like (reset variables):

There are C(m+n-1,m-1) lattice paths from (1,0) to (m,n) m>n. 
For any path which begins at (1,0) and *that touches the diagonal* we may interchange "up" moves and "across" moves (a reflection about y=x) before the first point of contact with the diagonal to give a unique path from (0,1) to (m,n). Also *every* path from (0,1) to (m,n) (of which there are C(m+n-1,n-1)) necessarily crosses the diagonal and may have the first portion of the path reflected to a path from (1,0) to (m,n). So there is a bijection between bad paths from (1,0) and (m,n) that *do touch the diagonal* and *all* C(m+n-1,n-1) paths from (0,1) to (m,n). Subtract these bad paths to give those that stay below and don't touch the diagonal

C(m+n-1,m-1) - C(m+n-1,n-1) = (((m-1)-(n-1))/(m+n))C(m+n,n) = ((m-n)/(m+n))C(m+n,n)

but this only counts those paths that stay below the diagonal. Note, however, that any path of this sort will *not* exceed the line y=x-1 so if we transform coordinates x'=x-1, y'=y then the new start and finish coordinates of our paths are (0,0) (m-1,n) and this path does not exceed the diagonal but may touch it. Then put m'=m-1, n'=n and the end of each path is (m',n') so there are

((m'-n'+1)/(m'+n'+1))C(m'+n'+1,n')

paths from (0,0) to (m',n') that do not exceed the diagonal.
Remove the primes for the result given above.

Trending News

Catalan Numbers and beyond!?

1 Answer