combinat::dyckWords
--
Dyck words
The library combinat::dyckWords
provides functions for counting,
generating, and manipulating Dyck words.
n
is a word with n
ones and n
zeroes such that in any prefix there are more
ones than zeroes.Cat::DecomposableClass
The MuPAD domain of Dyck words: DOM_LIST
The MuPAD type of prefix Dyck words.
isA(any type dw <, nonnegative integer n1, nonnegative integer n2>)
dw
is a Dyck word.dw
is a
a Dyck word of length 2n1
.dw
is a
(prefix) Dyck word of n1
opening parenthesis and n2
closing
parenthesis.
isAPrefix(any type dw <, nonnegative integer n1, nonnegative integer n2 >)
dw
is a prefix Dyck word.dw
is a
prefix Dyck word of n1
opening parenthesis and n2
closing
parenthesis.
count(nonnegative integer n)
n
, i.e. the
n-th Catalan number.
generator(nonnegative integer n)
n
.
list(nonnegative integer n)
n
.list(nonnegative integer n1, nonnegative integer n2)
n1
ones and n2
zeroes.
toString(Dyck word w)
w
, replacing "1" with "(" and "0" with ")". Note
that the function works even if the word is not well balanced.combinat::dyckWords::fromString
fromString(string s)
s
, replacing "(" with "1" and ")" with "0". Note
that the function does not check if the string is indeed well balanced.combinat::dyckWords::toString
toNonCrossingPartition(Dyck word w)
w
by the Biane bijection.combinat::nonCrossingPartitions
and
combinat::dyckWords::fromNonCrossingPartition
fromNonCrossingPartition(non crossing set partition p)
p
by the Biane bijection.combinat::dyckWords::toNonCrossingPartition
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])
"())(()" "(((())"
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
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]
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]}]
combinat::dyckWords::list
. See the example
section of combinat::integerVectors
for a way of building a
proper generator for Dyck words.
Ax::systemRep
MuPAD Combinat, an open source algebraic combinatorics package