View on
MetaCPAN is shutting down
For details read Perl NOC. After June 25th this page will redirect to
Mark Mertel > Math-DyckWords > Math::DyckWords



Annotate this POD

View/Report Bugs
Module Version: 0.03   Source  


Math::DyckWords - Perl module for generating Dyck words. Dyck words are named after the mathematician Walther von Dyck.


  use Math::DyckWords qw( dyck_words_by_lex
                          catalan_number );

  @words = dyck_words_by_lex( 4 );
  @words = dyck_words_by_position( 4 );
  @words = dyck_words_by_swap( 4 );
  $rank  = ranking( '01010101' );
  $word  = unranking( 3, 2 );


Dyck words are even numbered string of X's and Y's, or 0's and 1's, or any other binary alphabet for that matter, such that no initial segment has more Y's or 1's. The following are the Dyck words of length 2n where n = 3:


Another common use of Dyck words is in dealing with the balanced parenthesis problem. Substituting the left and right parentheses for the 0's an 1's listed above we have:


There is also a relationship between Dyck words and Catalan numbers. Catalan numbers have many applications in combinatorics and consists of a sequence of ever increasing integers following the formula:


The first few numbers in the Catalan sequence are:

    1, 1, 2, 5, 14, 132, 429, 1430, 4862, 16796, 58786, 208012

The relationship between Dyck words and the Catalan sequence can be easily seen as the nth Catalan number is equal to the number of permutations, or unique Dyck words of length 2n. For example, the 3rd Catalan number, using a zero index, is 5. This is the same number of Dyck words of length 2n where n = 3.

The algorithms in this module are based on those presented in the scholarly paper "Generating and ranking of Dyck words" by Zoltan Kasa available on-line at, and the provide three different Dyck word generators - lexigraphical, positional, and one that generates Dyck words by swapping characters.


None by default.


dyck_words_by_lex( $n )

This algorithm returns a list of all Dyck words of length 2n in ascending lexicographic order, i.e. 000111, 001011, 001101, 010011, 010101

dyck_words_by_position( $n )

This algorithm returns a list of all Dyck words of length 2n in descending lexicographic order, i.e. 010101, 010011, 001101, 001011, 000111.

translate_positions( @p )

This function translates an array of integer values indicating the position of 1's in the resultant Dyck word, and is called by the dyck_words_by_position function.

dyck_words_by_position( $n )

This algorithm returns a list of all Dyck words of length 2n in no particular order, i.e. 010101, 001101, 001011, 000111, 010011. This is done by changing the first occurrence of '10' to '01'.

monotonic_path_count( $n, $i, $j )

Ranking Dyck words means to determine the position of a Dyck word in a given ordered sequence of all Dyck words. For ranking these words we will use the following function, where f(n,i,j) represents the number of paths between (0,0) and (i,j) not crossing the diagonal x = y of the grid.

positions( $w )

This function converts a Dyck word string of 1's and 0's into a list of positions where the 1's are located, i.e. 2468 => 01010101

ranking( $w )

This function returns the rank of an individual Dyck word $w in the list of all Dyck words of the same length.

unranking( $n, $r )

This function returns the rank $r Dyck word of length $n.

catalan_number( $n )

Using the formula - (2n)!/(n!(n+1)!) - this function returns the corresponding number $n from the Catalan sequence.

syntax highlighting: