How many ways can you walk from A to B such that you always stay below the diagonal? (more details included)?

Question

There is a square grid. In the lower left corner is A and in the upper right is B. A diagonal is drawn from A to B and you are not allowed to go above it while travelling from A to B. You can only move right and up. In how many ways in an n x n grid can you travel from A to B? Prove your answer.

(I know that without the diagonal, there are (2n) C (n) ways.)

Answer 1

The answer is the nth catalan number - (2n C n)/(n+1).
There are several ways to prove this. Heres my favourite:

Lets consider instead the number of paths which *do* cross the diagonal. Lets look at the first point on this path which lies above the diagonal - at this moment in time, we have gone up one more time than we have gone right.

'Flip' everything from this point onwards - ie, instead of going up, go right, and vice versa.

You end up with a (n-1)x(n+1) grid, where you have a path from the bottom left to the top right, which crosses the diagonal (at the same point).

Now, if you work backwards - you know every path in a (n-1)x(n+1) grid *must* cross the diagonal somewhere - so each one of these paths corresponds exactly to a diagonal-crossing path in our original problem.

There are (n-1+n+1)C(n-1) = (2n)C(n-1) such paths in the new grid, so there must be (2n)C(n-1) diagonal-crossing paths in the original grid.

Thus subtract this from the total number of paths, and the answer must be (2n)C(n) - (2n)C(n-1). That simplifies to the catalan number formula.

If you google for Catalan Number, I'm sure you'll find other proofs, since that number comes up all over the place.