Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
4  
Okay, I think I got it: math.stackexchange.com/questions/22999/… –  Arturo Magidin Apr 19 '11 at 19:21
add comment

2 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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