NAME

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

SYNOPSIS

  use Math::DyckWords qw( dyck_words_by_lex
                          dyck_words_by_position
                          dyck_words_by_swap
                          ranking
                          unranking
                          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 );

DESCRIPTION

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:

    000111
    010011
    010101
    001101
    001011

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:

    (2n)!/(n!(n+1)!)

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 http://arxiv4.library.cornell.edu/pdf/1002.2625, and the provide three different Dyck word generators - lexigraphical, positional, and one that generates Dyck words by swapping characters.

EXPORT

None by default.

FUNCTIONS

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.