Dyck Word Generator

Dyck word generator is a utility that lexicographically generate a sequence of Dyck words for specific lengthn. The algorithm used was designed by Kostas Manes and me.

Catalan Number & Dyck Words

Source: wikipedia - Catalan number

There are many counting problems in combinatorics whose solution is given by the Catalan numbers. The book Enumerative Combinatorics: Volume 2 by combinatorialist Richard P. Stanley contains a set of exercises which describe 66 different interpretations of the Catalan numbers. Following are some examples, with illustrations of the case C₃ = 5.

• C_n is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's (see also Dyck language). For example, the following are the Dyck words of length 6:

XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.

• Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, C_n counts the number of expressions containing n pairs of parentheses which are correctly matched:

((()))     ()(())     ()()()     (())()     (()())

• C_n is the number of different ways n + 1 factors can be completely parenthesized (or the number of ways of associating n applications of a binary operator). For n = 3 for example, we have the following five different parenthesizations of four factors:

Download & Usage

Here you can download binaries for:

• Windows
• Mac OS X (intel)
• Linux

Its usage is rather simple:

nsp <length>

For the output a binary format is used and the result are stored in file output.result. The source code is not available. Be advised that this implementation uses double for the calculation of the Catalan number. Consequently, this will not work accurately when the length exceeds the data type's capacity. This will be fixed in future releases.