Catalan number
Third proof

This bijective proof provides a natural explanation for the term n + 1 appearing in the denominator of the formula for C. A generalized version of this proof can be found in a paper of Rukavicka Josef (2011).

Given a monotonic path, the exceedance of the path is defined to be the number of vertical edges above the diagonal. For example, in Figure 2, the edges above the diagonal are marked in red, so the exceedance of this path is 5.

Given a monotonic path whose exceedance is not zero, we apply the following algorithm to construct a new path whose exceedance is 1 less than the one we started with.

In Figure 3, the black dot indicates the point where the path first crosses the diagonal. The black edge is X, and we place the last lattice point of the red portion in the top-right corner, and the first lattice point of the green portion in the bottom-left corner, and place X accordingly, to make a new path, shown in the second diagram.

The exceedance has dropped from 3 to 2. In fact, the algorithm causes the exceedance to decrease by 1 for any path that we feed it, because the first vertical step starting on the diagonal (at the point marked with a black dot) is the only vertical edge that changes from being above the diagonal to being below it when we apply the algorithm - all the other vertical edges stay on the same side of the diagonal.

It can be seen that this process is reversible: given any path P whose exceedance is less than n, there is exactly one path which yields P when the algorithm is applied to it. Indeed, the (black) edge X, which originally was the first horizontal step ending on the diagonal, has become the last horizontal step starting on the diagonal. Alternatively, reverse the original algorithm to look for the first edge that passes below the diagonal.

This implies that the number of paths of exceedance n is equal to the number of paths of exceedance n − 1, which is equal to the number of paths of exceedance n − 2, and so on, down to zero. In other words, we have split up the set of all monotonic paths into n + 1 equally sized classes, corresponding to the possible exceedances between 0 and n. Since there are (2 n n) {\displaystyle \textstyle {2n \choose n}} monotonic paths, we obtain the desired formula C n = 1 n + 1 (2 n n). {\displaystyle \textstyle C_{n}={\frac {1}{n+1}}{2n \choose n}.}

Figure 4 illustrates the situation for n = 3. Each of the 20 possible monotonic paths appears somewhere in the table. The first column shows all paths of exceedance three, which lie entirely above the diagonal. The columns to the right show the result of successive applications of the algorithm, with the exceedance decreasing one unit at a time. There are five rows, that is C = 5, and the last column displays all paths no higher than the diagonal.

Using Dyck words, start with a sequence from (2 n n) {\displaystyle \textstyle {\binom {2n}{n}}}. Let X d {\displaystyle X_{d}} be the first X that brings an initial subsequence to equality, and configure the sequence as (F) X d (L) {\displaystyle (F)X_{d}(L)}. The new sequence is L X F {\displaystyle LXF}.
detectable_content:postscript