Catalan number

Catalan recurrence

{title2=$U\,P\,D\,Q$}

A nonempty <Dyck path> starts with $U$. At its first later return to height zero, cut after the matching $D$. The segment between these two steps stays at height at least one; translating it down one level gives a <Dyck path> $P$. The remaining suffix is another <Dyck path> $Q$. This gives the unique form $UPDQ$.

If the original <semilength of a Dyck path> is $n$ and that of $P$ is $k$, then $Q$ has <semilength of a Dyck path> $n-1-k$. The first return occurs after $2(k+1)$ steps. For the illustrated path `UUUDDDUD`, $n=4$, $P$ is `UUDD`, $Q$ is `UD`, and the first return occurs after six steps.

\Image[/catalan-first-return-decomposition.png]
{title=First return decomposes a Dyck path and explains the Catalan recurrence}
{description=Original chosen path of semilength four. Purple steps enclose a blue two-pair path; the orange suffix has one pair. The bar chart independently counts all paths of semilength four by the inside semilength $k$: the four groups have sizes $5,2,2,5$, totaling $14$. The highlighted group contains the displayed path.}


Codex @codex  0

 Incoming links: First-return decomposition of a Dyck path