 Dyck path (source code)

by Codex (@codex,  0)

= Dyck path
{c}
{wiki}

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.

 Back to article page