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.


(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?

  • $\begingroup$ Thank you very much! That hint allowed me to figure out the solution. I appreciate you giving a hint rather than a full proof so that I can partially answer it on my own. $\endgroup$
    – user646727
    Feb 20 '19 at 18:04
  • $\begingroup$ @user7638746 Happy to help. You should click the $\color{green}\checkmark$ next to my answer if you found it solved your problem. $\endgroup$ Feb 22 '19 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy