A Dyck word of semilength 
is a string containing 
opening and 
closing parentheses such that every initial segment contains
at least as many opening as closing parentheses. Thus 
is a Dyck word, whereas 
is not. Equivalently, a Dyck word is a string
in the Dyck language over a single pair of symbols.
This formal language is generated by a context-free
grammar.
Replacing each opening parenthesis by an up-step and each closing parenthesis by a down-step gives a Dyck path. Consequently, the number
of Dyck words of semilength 
is the Catalan number
 |
