Editing Catalan number (section)

=== Sixth proof ===

This proof is based on the [[Dyck language|Dyck words]] interpretation of the Catalan numbers and uses the [[cycle lemma#Proof_by_the_cycle_lemma|cycle lemma]] of Dvoretzky and Motzkin.<ref>{{citation | last1 = Dershowitz | first1 = Nachum | last2 = Zaks | first2 = Shmuel | year =1980 | title = Enumerations of ordered trees| journal = Discrete Mathematics | volume = 31 | pages = 9–28 | doi=10.1016/0012-365x(80)90168-5| hdl = 2027/uiuo.ark:/13960/t3kw6z60d | hdl-access = free }}</ref><ref>{{citation | last1 =Dvoretzky| first1= Aryeh| last2= Motzkin| first2=Theodore |year=1947| title =A problem of arrangements|journal= Duke Mathematical Journal| volume = 14| issue= 2|pages = 305–313| doi=10.1215/s0012-7094-47-01423-3}}</ref>

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<ref>{{cite journal |last1=Dershowitz |first1=Nachum |last2=Zaks |first2=Shmuel |title=The Cycle Lemma and Some Applications |journal=European Journal of Combinatorics |date=January 1990 |volume=11 |issue=1 |pages=35–40 |doi=10.1016/S0195-6698(13)80053-4 |url=http://www.cs.tau.ac.il/~nachumd/papers/CL.pdf }}</ref> states that any sequence of <math>m</math> X's and <math>n</math> Y's, where <math>m> n</math>, has precisely <math>m-n</math> dominating [[circular shift]]s. To see this, arrange the given sequence of <math>m+n</math> X's and Y's in a circle. Repeatedly removing XY pairs leaves exactly <math>m-n</math> X's. Each of these X's was the start of a dominating circular shift before anything was removed. For example, consider <math>\mathit{XXYXY}</math>. This sequence is dominating, but none of its circular shifts <math>\mathit{XYXYX}</math>, <math>\mathit{YXYXX}</math>, <math>\mathit{XYXXY}</math> and <math>\mathit{YXXYX}</math> are.

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