The Second Proof of the Catalan Numbers
This is a note about the second proof of the Catalan numbers on wikipedia. The n-th Catalan number is the number of monotonic paths along the edges of an n by n grid that does not cross the diagonal. A monotonic path on an n by n grid, where n is assumed an integer, is a path formed from the origin (0, 0) to the destination (n, n) by either going up or going to the right. The diagonal mentioned above is the line drawn from (0, 0) to (n, n).
Proof #
Consider the number of all monotonic paths from (0, 0) to (n, n).
Any such a path can be described uniquely by a string of Xs and Ys,
where X represents moving right and Y represents moving up.
Since each path is monotonic, the length of such a string is 2n (move up n times + move right n times).
Since there are only two symbols, namely X and Y, once the positions of one symbol is determined,
the other symbol fills the rest automatically.
Thus, the total number of possible monotonic paths on an n by n grid is
Consider any particular but general monotonic path on an n by n grid that crosses the diagonal.
Call the first position in the path that goes above the diagonal (a, b).
Notice
Let us define this flipping process as a function
Now observe that any monotonic path on n - 1 by n + 1 grid must cross
the diagonal drawn from (0, 0) to (n - 1, n - 1) since it must reach (n - 1, n + 1).
Call the first position in the path that goes to the right of the diagonal (c, d).
Notice
Thus, the set of all monotonic paths on an n by n grid that cross the diagonal and the set of all monotonic paths on an n - 1 by n + 1 grid have a one-to-one correspondence.
The number of all possible monotonic paths on an n - 1 by n + 1 grid is:
It can be shown algebraically that the above is equivalent to