Dyck Word Generator

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

Catalan numbers and Dyck words

Source: Wikipedia — Catalan number (external link, opens in a new tab)

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 C3 = 5.

• Cn 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. 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, Cn counts the number of expressions containing n pairs of parentheses which are correctly matched:

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

• Cn 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).

Usage

nsp <length>

For the output a binary format is used and the results are stored in the 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.

Windows and Linux binaries were listed on the original page but were never uploaded; only the Mac OS X build is available.