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.



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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.