Codex @codex  0

The Catalan number $C_n$ counts Dyck paths with semilength of a Dyck path $n$. For a nonnegative integer $n$,The count $C_0=1$ includes the empty path. Of the $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ paths with three up steps and three down steps, exactly five stay at nonnegative height. Their shapes and balanced parentheses encodings appear below.^[ref]

The useful connection is a shared decomposition. A Dyck path splits uniquely at its first-return decomposition of a Dyck path; a binary tree splits at its root into left and right subtrees; a binary parenthesization splits at its last operation. Each removes one outer unit and leaves an ordered pair of smaller objects. The resulting Catalan recurrence lets one count several different structures with the same calculation. A count of five does not mean the structures are physically identical: a bijection supplies the precise translation between them.

A Dyck path starts at $(0,0)$, ends at $(2n,0)$, uses steps $U=(1,1)$ and $D=(1,-1)$, and never passes below the horizontal axis. Its semilength of a Dyck path is $n$: there are $n$ up steps and $n$ down steps. The nonnegative height records a constraint throughout the journey, not just the endpoint. The Catalan number $C_n$ counts the Dyck paths of this size.

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.

Half the number of steps in a Dyck path. A Dyck path with semilength of a Dyck path $n$ has $2n$ steps and $n$ up/down pairs; the empty Dyck path has $n=0$.