Dyck Path w/ Descents of Length 2

169 Views Asked by At

Prove the number of Dyck paths with $4n$ steps such that every descent is of length exactly two is equal to the Catalan number $C_n$.


I have drawn out some examples to try and solve the problem and have noticed some patterns, but I can not see any obvious bijection or recurrence.

1

There are 1 best solutions below

2
On BEST ANSWER

(Big) Hint

I will think of a Dyck path as a string of $+$s and $-s$ where every prefix has at least as many $+$s as $-s$.

In a Dyck path where every descent has length $2$, the $-$s appear in pairs, and each pair $--$ is preceded by a $+$. Replace each occurrence of $+--$ with a $-$. What properties does the resulting string have? Is this transformation reversible?