[Previous] [Next] [Contents]

combinat::dyckWords -- Dyck words

Introduction

The library combinat::dyckWords provides functions for counting, generating, and manipulating Dyck words.

Details

Categories

Cat::DecomposableClass

Related Domains

combinat::binaryTrees

Entries

domtype

The MuPAD domain of Dyck words: DOM_LIST

typePrefix

The MuPAD type of prefix Dyck words.

Method isA: test if an object is a Dyck word

Method isAPrefix: test if an object is a prefix Dyck word

Method count: number of Dyck words

Method generator: generator for Dyck words

Method list: list of the Dyck words

Method toString: conversion to string of well balanced parenthesis

Method fromString: conversion from string of well balanced parenthesis

Method toNonCrossingPartition: Biane bijection to non crossing set partitions

Method fromNonCrossingPartition: Biane bijection from non-crossing set partitions

Example 1

There are 5 Dyck words of size 3:

>> combinat::dyckWords::count(3)
     
                                     5
        

Here is the list:

>> combinat::dyckWords::list(3)
     
      [[1, 1, 1, 0, 0, 0], [1, 1, 0, 1, 0, 0], [1, 1, 0, 0, 1, 0],
      
         [1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 1, 0]]
        

They correspond to the 5 strings of well-balanced parenthesis of length 6:

>> map(combinat::dyckWords::list(3), combinat::dyckWords::toString)
     
            ["((()))", "(()())", "(())()", "()(())", "()()()"]
        

On the other hand, neither [1,0,0,1,1,0] nor [1,1,1,1,0,0] are Dyck words:

>> combinat::dyckWords::toString([1,0,0,1,1,0]);
   combinat::dyckWords::toString([1,1,1,1,0,0])
     
                                 "())(()"
      
                                 "(((())"
        

Example 2

In this example we check the type of some Dyck words.

>> combinat::dyckWords::isA([1, 1, 1, 0, 0, 0]);
   combinat::dyckWords::isA([1, 1, 1, 0, 0, 0], 3);
   combinat::dyckWords::isA([1, 1, 1, 0, 0, 0], 2);
     
                                   TRUE
       
                                   TRUE
       
                                   FALSE
        

The list [1,0,0,1,1,0] is not a Dyck word:

>> combinat::dyckWords::isA([1, 0, 0, 1, 1, 0]); 
   combinat::dyckWords::isA([1, 0, 0, 1, 1, 0], 3); 
     
                                   FALSE
       
                                   FALSE
        

The list [1,1,1,1,0,0] is not a Dyck word, but a prefix Dyck word:

>> combinat::dyckWords::isA([1, 1, 1, 1, 0, 0]);
   combinat::dyckWords::isA([1, 1, 1, 1, 0, 0], 4, 2);
   combinat::dyckWords::isAPrefix([1, 1, 1, 1, 0, 0]); 
   combinat::dyckWords::isAPrefix([1, 1, 1, 1, 0, 0], 4, 2);
     
                                   FALSE
       
                                   TRUE
       
                                   TRUE
       
                                   TRUE
        

Example 3

One can convert a Dyck word to a string of well-balanced parenthesis:

>> combinat::dyckWords::toString([1,1,1,0,1,1,0,0,0,1,0,0,1,1,1,0,0,0,1,0]);
     
                          "((()(()))())((()))()"
        

And convert it back:

>> combinat::dyckWords::fromString("((()(()))())((()))()");
     
       [1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0]
        

Example 4

Dyck words of size n are in bijection with non-crossing set partitions of 1, 2, ..., n. Here is the the image of [1,0,1,0,1,0] by the Biane bijection:

>> combinat::dyckWords::toNonCrossingPartition([1,0,1,1,0,0,1,0])
     
                            {[1], [4], [2, 3]}
        

We can reconstruct the original Dyck word:

>> combinat::dyckWords::fromNonCrossingPartition({[1], [4], [2, 3]})
     
                         [1, 0, 1, 1, 0, 0, 1, 0]
        

Here is the list of all non-crossing set partitions of 1, 2, 3:

>> map(combinat::dyckWords::list(3),
       combinat::dyckWords::toNonCrossingPartition)
     
      [{[1, 2, 3]}, {[2], [1, 3]}, {[3], [1, 2]}, {[1], [2, 3]},
      
         {[1], [2], [3]}]
        

Background

Super-Domain

Dom::BaseDomain

Axioms

Ax::systemRep

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package