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

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!

-
This is just a recasting of Bertrand' Ballot Problem en.wikipedia.org/wiki/Ballot_problem I'm sure we've had this before, but I can't seem to locate it. See also webspace.ship.edu/msrenault/ballotproblem/… –  Arturo Magidin Apr 19 '11 at 19:20
Okay, I think I got it: math.stackexchange.com/questions/22999/… –  Arturo Magidin Apr 19 '11 at 19:21

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.

-

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).

-