Skip to main content

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 (n+nn)=(2nn).

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 (a,b)=(a,a+1) since b must be greater than a and it's the first such a position. Now flip the remaining path along the diagonal; i.e. in strings of Xs and Ys, replace all Xs by Ys and all Ys by Xs simultaneously. Originally, the remaining path had n - a steps to move right and n(a+1)=na1 steps to move up. After flipping the path, it has n - a steps to move up and na1 steps to move right. Since the remaining path starts at (a,a+1), the destination of the resultant path is (a+(na1),a+1+(na))=(n1,n+1).

Let us define this flipping process as a function f1 from the set of all monotonic paths on an n by n grid that cross the diagonal to the set of all monotonic paths on an n - 1 by n + 1 grid. This function is one-to-one since replacing Xs by Ys and Ys by Xs does not affect the uniqueness of any path.

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 (c,d)=(c,c1) since d must be greater than c and it's the first such a position. Let us define a new function f2 that flips the remaining path along the diagonal by replacing Xs by Ys and Ys by Xs as done before. It can be shown that the resultant path will reach (n, n). Again, this function is one-to-one since replacing Xs by Ys and Ys by Xs does not affect the uniqueness of any path, and every monotonic path on n - 1 by n + 1 grid is unique.

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: ((n1)+(n+1)n1)=(2nn1)=(2nn+1) Because there is a one-to-one correspondence, this is the number of monotonic paths on a n by n grid that crosses the diagonal. Thus, the number of monotonic paths on a n by n grid that does not cross the diagonal, and thereby the n-th Catalan number Cn is: (2nn)(2nn1)=(2nn)(2nn+1)

It can be shown algebraically that the above is equivalent to 1n+1(2nn) Q.E.D.