5
$\begingroup$

Count the number of paths from $(0,0)$ to $(2n,n)$ than never go above $y=x$

At first I thought of the problem by expanding the graph to $(0,0)$ to $(2n,2n)$ and messing around with adding and subtracting multiples of the Catalan number formula, but I feel this is far too rudimentary and in doing so I am leaving out many paths that move through the $x=n$ to $x=2n$ and $y=0$ to $y=n$ square section of the graph that has no restrictions (because the diagonal cuts off at $(n,n)$). Of course, you can only go right and up.

Thanks!

  • 4
    Okay, I think I got it: http://math.stackexchange.com/questions/22999/how-many-ways-can-we-let-people-into-a-movie-theater-if-they-only-have-half-dolla2011-04-19

2 Answers 2

1

The Ballot theorem says

In an election where candidate A receives $p$ votes and candidate B $q$ votes with $p$ > $q$, the probability that A will be strictly ahead of B throughout the count is $\dfrac{p-q}{p+q}$

So if you had asked "Count the number of paths from $(0,0)$ to $(2n,n)$ than never touch $y=x$" then the answer would have been $\dfrac{n}{3n} {3n \choose n}$ which can be slightly simplified.

But you want "never go above $y=x$" and this is equivalent to counting the paths from $(-1,0)$ to $(2n,n)$ that never touch $y=x+1$, equivalently the paths from $(0,0)$ to $(2n+1,n)$ that never touch $y=x$.

Since this may be homework, perhaps you should try a little to finish this off.

0

The most straightforward way of doing this seems to be to partition based on where the paths cross over from $x=n$ to $x=n+1$ and then staple together the two calculations: first, how many paths from $(0,0)$ to $(n, k)$ ($k \leq n$) never go above the diagonal (this should be feasible through versions of the usual machinations that bring you to the Catalan numbers), and then how many paths there are from $(n+1, k)$ to $(2n, n)$ (which is, of course, the same as the number of paths from $(0, 0)$ to $(n-1, n-k)$ and is readily evaluated).