6
$\begingroup$

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!

  • 0
    This is just a recasting of Bertrand' Ballot Problem http://en.wikipedia.org/wiki/Ballot_problem I'm sure we've had this before, but I can't seem to locate it. See also http://webspace.ship.edu/msrenault/ballotproblem/Four%20Proofs%20of%20the%20Ballot%20Theorem.pdf2011-04-19
  • 4
    Okay, I think I got it: http://math.stackexchange.com/questions/22999/how-many-ways-can-we-let-people-into-a-movie-theater-if-they-only-have-half-dolla2011-04-19

2 Answers 2