Editing Catalan number (section)

=== Second proof ===
{{See also|Method of images#Mathematics for discrete cases}}

[[File:Catalan number-path reflection.svg|thumb|upright=0.5|Figure 1. The invalid portion of the path (dotted red) is flipped (solid red). Bad paths (after the flip) reach {{math|(''n'' – 1, ''n'' + 1)}} instead of {{math|(''n'', ''n'')}}.]]

We count the number of paths which start and end on the diagonal of an {{math|''n'' × ''n''}} grid. All such paths have {{mvar|n}} right and {{mvar|n}} up steps. Since we can choose which of the {{math|2''n''}} steps are up or right, there are in total <math>\tbinom{2n}{n}</math> monotonic paths of this type. A ''bad'' path crosses the main diagonal and touches the next higher diagonal (red in the illustration).

The part of the path after the higher diagonal is then flipped about that diagonal, as illustrated with the red dotted line. This swaps all the right steps to up steps and vice versa. In the section of the path that is not reflected, there is one more up step than right steps, so therefore the remaining section of the bad path has one more right step than up steps. When this portion of the path is reflected, it will have one more up step than right steps.

Since there are still {{math|2''n''}} steps, there are now {{math|''n'' + 1}} up steps and {{math|''n'' − 1}} right steps. So, instead of reaching  {{math|(''n'', ''n'')}}, all bad paths after reflection end at {{math|(''n'' − 1, ''n'' + 1)}}. Because every monotonic path in the {{math|(''n'' − 1) × (''n'' + 1)}} grid meets the higher diagonal, and because the reflection process is reversible, the reflection is therefore a bijection between bad paths in the original grid and monotonic paths in the new grid.

The number of bad paths is therefore:

:<math>{n-1 + n+1 \choose n-1} = {2n \choose n-1} = {2n \choose n+1}</math>

and the number of Catalan paths (i.e. good paths) is obtained by removing the number of bad paths from the total number of monotonic paths of the original grid,

:<math>C_n = {2n \choose n} - {2n \choose n+1} = \frac{1}{n+1}{2n \choose n}.</math>

In terms of Dyck words, we start with a (non-Dyck) sequence of {{mvar|n}} X's and {{mvar|n}} Y's and interchange all X's and Y's after the first Y that violates the Dyck condition. After this Y, note that there is exactly one more Y than there are Xs.