[Previous] [Next] [Contents]

## `combinat::dyckWords` -- Dyck words

#### Introduction

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

#### Details

- A Dyck word of size `n` is a word with `n` ones and `n` zeroes such that in any prefix there are more ones than zeroes.

- A Dyck word can be interpreted as a word of well balanced parenthesis by substituting ones with opening parenthesis and zeroes with closing parenthesis.

- A prefix Dyck word is a non completed Dyck word, that is, a word with more opening parenthesis than closing parenthesis.

- Geometrically, a Dyck word is also a discrete path in the nonnegative plane N×N, going from (0,0) to (2n,0), with right-up steps (ones) and right-down steps (zeroes).

- Dyck words of length 2n are in bijection with many other discrete classes like rooted ordered trees on n+1 nodes, binary trees on n nodes, complete binary trees on 2n+1 nodes, n+2-gone triangulations, standard tableaux with 2 lines of width n or 2 columns of height n, non crossing set partitions of {1,...,n}, etc. They are counted by the Catalan numbers.

#### 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

- `isA(any type dw <, nonnegative integer n1, nonnegative integer n2>)`

- Returns whether the object `dw` is a Dyck word.
- If the optional argument is present, returns whether `dw` is a a Dyck word of length 2`n1`.
- If the two optional arguments are present, returns whether `dw` is a (prefix) Dyck word of `n1` opening parenthesis and `n2` closing parenthesis.

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

- `isAPrefix(any type dw <, nonnegative integer n1, nonnegative integer n2 >)`

- Returns whether the object `dw` is a prefix Dyck word.
- If the optional arguments are present, returns whether `dw` is a prefix Dyck word of `n1` opening parenthesis and `n2` closing parenthesis.

#### Method count: number of Dyck words

- `count(nonnegative integer n)`

- Returns the number of Dyck words of size `n`, i.e. the n-th Catalan number.

#### Method generator: generator for Dyck words

- `generator(nonnegative integer n)`

- Returns a generator for Dyck words of size `n`.

#### Method list: list of the Dyck words

- `list(nonnegative integer n)`

- Returns the list of Dyck words of size `n`.

- `list(nonnegative integer n1, nonnegative integer n2)`

- Returns the list of prefix Dyck words, with `n1` ones and `n2` zeroes.

#### Method toString: conversion to string of well balanced parenthesis

- `toString(Dyck word w)`

- Returns the string of well balanced parenthesis corresponding to the Dyck word `w`, replacing "1" with "(" and "0" with ")". Note that the function works even if the word is not well balanced.
- See also the function `combinat::dyckWords::fromString`

#### Method fromString: conversion from string of well balanced parenthesis

- `fromString(string s)`

- Returns the Dyck word corresponding to the string of well balanced parenthesis `s`, replacing "(" with "1" and ")" with "0". Note that the function does not check if the string is indeed well balanced.
- See also `combinat::dyckWords::toString`

#### Method toNonCrossingPartition: Biane bijection to non crossing set partitions

- `toNonCrossingPartition(Dyck word w)`

- Returns the non-crossing set partition corresponding to the Dyck word `w` by the Biane bijection.
- See also `combinat::nonCrossingPartitions` and `combinat::dyckWords::fromNonCrossingPartition`
- Reference: Philippe Biane, Permutations suivant le type d'excédances et le nombre d'inversions et interprétation combinatoire d'une fraction continue de Heine, Europ. J. Comb., 14(4): 277-284, 1993

#### Method fromNonCrossingPartition: Biane bijection from non-crossing set partitions

- `fromNonCrossingPartition(non crossing set partition p)`

- Returns the Dyck word corresponding to the non crossing set partition `p` by the Biane bijection.
- See also `combinat::dyckWords::toNonCrossingPartition`

#### 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

- Dyck words are naturally ordered lexicographically.

- The current implementation of the generator is not optimized, and simply uses `combinat::dyckWords::list`. See the example section of `combinat::integerVectors` for a way of building a proper generator for Dyck words.

#### Super-Domain

`Dom::BaseDomain`

#### Axioms

`Ax::systemRep`

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package