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

combinatorics

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!

Best Answer

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.