Dyck Word GeneratorDyck word generator is a utility that lexicographically generate a sequence of Dyck words for specific length
n. The algorithm used was designed by Kostas Manes and me.
Catalan Number & Dyck WordsSource: 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 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 (see also Dyck language). For example, the following are the Dyck words of length 6:
- 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). For n = 3 for example, we have the following five different parenthesizations of four factors:
Download & UsageHere you can download binaries for:
- Mac OS X (intel)
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
doublefor 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.