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!
 A: 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. 
A: 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).
