stylistic:style_transfer, structural:reformatting
Sixth proof

This proof is based on the Dyck words interpretation of the Catalan numbers and uses the cycle lemma of Dvoretzky and Motzkin.

We call a sequence of X's and Y's dominating if, reading from left to right, the number of X's is always strictly greater than the number of Y's. The cycle lemma states that any sequence of m {\displaystyle m} X's and n {\displaystyle n} Y's, where m > n {\displaystyle m>n}, has precisely m − n {\displaystyle m-n} dominating circular shifts. To see this, arrange the given sequence of m + n {\displaystyle m+n} X's and Y's in a circle. Repeatedly removing XY pairs leaves exactly m − n {\displaystyle m-n} X's. Each of these X's was the start of a dominating circular shift before anything was removed. For example, consider X X Y X Y {\displaystyle {\mathit {XXYXY}}}. This sequence is dominating, but none of its circular shifts X Y X Y X {\displaystyle {\mathit {XYXYX}}}, Y X Y X X {\displaystyle {\mathit {YXYXX}}}, X Y X X Y {\displaystyle {\mathit {XYXXY}}} and Y X X Y X {\displaystyle {\mathit {YXXYX}}} are.

A string is a Dyck word of n {\displaystyle n} X's and n {\displaystyle n} Y's if and only if prepending an X to the Dyck word gives a dominating sequence with n + 1 {\displaystyle n+1} X's and n {\displaystyle n} Y's, so we can count the former by instead counting the latter. In particular, when m = n + 1 {\displaystyle m=n+1}, there is exactly one dominating circular shift. There are (2 n + 1 n) {\displaystyle \textstyle {2n+1 \choose n}} sequences with exactly n + 1 {\displaystyle n+1} X's and n {\displaystyle n} Y's. For each of these, only one of the 2 n + 1 {\displaystyle 2n+1} circular shifts is dominating. Therefore there are 1 2 n + 1 (2 n + 1 n) = C n {\displaystyle \textstyle {\frac {1}{2n+1}}{2n+1 \choose n}=C_{n}} distinct sequences of n + 1 {\displaystyle n+1} X's and n {\displaystyle n} Y's that are dominating, each of which corresponds to exactly one Dyck word.