Dyck word

Remarks

Other common alphabets are $\{(, )\}$ and $\{[, ]\}$. Then the Dyck words are the balanced strings of brackets. The Dyck words of semilength $2$ are $UUDD$ and $UDUD$. Read $U$ as a step $(1, 1)$ and $D$ as a step $(1, -1)$. A Dyck word is then a lattice path from $(0, 0)$ to $(2n, 0)$ that never goes below the horizontal axis. The Dyck words of semilength $n$ are counted by the Catalan number $C_n$.