% $Id: dyckWords.tex,v 1.1.1.7 2004/10/04 17:25:16 nthiery Exp $
\begin{Mhelppage}{dyckWords}{F.~Hivert and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{nthiery}{21.09.2003}{proofread}

\begin{MInfo}
  \eng{Dyck words}
\end{MInfo}


\begin{MIntro}
  \eng{The library \Mthis{} provides functions for counting,
    generating, and manipulating Dyck words.}
\end{MIntro}

\MKeywords{combinatorics,Dyck word,catalan}

\begin{MDetails}
  \eng{A \emph{Dyck word} of size \Mpar{n} is a word with \Mpar{n}
    ones and \Mpar{n} zeroes such that in any prefix there are more
    ones than zeroes.}
  
  \eng{A Dyck word can be interpreted as a word of well balanced
    parenthesis by substituting ones with opening parenthesis and
    zeroes with closing parenthesis.}

  \eng{A \emph{prefix Dyck word} is a non completed Dyck word, that is,
    a word with more opening parenthesis than closing parenthesis.}
    
  \eng{Geometrically, a Dyck word is also a discrete path in the
    nonnegative plane $\mathbb{N}\times\mathbb{N}$, going from $(0,0)$
    to $(2n,0)$, with right-up steps (ones) and right-down steps
    (zeroes).}
  
  \eng{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,\dots,n\}$, etc. They are counted by the
    Catalan numbers.}
\end{MDetails}

\begin{MCategories}
\Mex{Cat::DecomposableClass}
\end{MCategories}

\MRelatedDomains{combinat::binaryTrees}

\begin{MDomEntries}
  \MDomEntry{domtype}
  \eng{The \mupad\ domain of Dyck words: \Mup{DOM_LIST}}
  \MDomEntry{typePrefix}
     \eng{The \mupad\ type of prefix Dyck words.}
\end{MDomEntries}

\begin{MMethodDetails}{isA}
  \infoEng{test if an object is a Dyck word}
  \call{\Mtype{any type} dw\Mopt{, \Mtype{nonnegative integer} n1, \Mtype{nonnegative integer} n2}}
  \eng{Returns whether the object \Mpar{dw} is a Dyck word.}
  \eng{If the optional argument is present, returns whether \Mpar{dw} is a
   a Dyck word of length 2\Mpar{n1}.}
  \eng{If the two optional arguments are present, returns whether \Mpar{dw} is a
   (prefix) Dyck word of \Mpar{n1} opening parenthesis and \Mpar{n2} closing
   parenthesis.}
\end{MMethodDetails}

\begin{MMethodDetails}{isAPrefix}
  \infoEng{test if an object is a prefix Dyck word}
  \call{\Mtype{any type} dw\Mopt{, \Mtype{nonnegative integer} n1, \Mtype{nonnegative integer} n2 }}
  \eng{Returns whether the object \Mpar{dw} is a prefix Dyck word.}
  \eng{If the optional arguments are present, returns whether \Mpar{dw} is a
   prefix Dyck word of \Mpar{n1} opening parenthesis and \Mpar{n2} closing
   parenthesis.}
\end{MMethodDetails}

\begin{MMethodDetails}{count}
  \infoEng{number of Dyck words}%
  \call{\Mtype{nonnegative integer} n}%
  \eng{Returns the number of Dyck words of size \Mpar{n}, i.e. the
    $n$-th Catalan number.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for Dyck words}
  \call{\Mtype{nonnegative integer} n}
  \eng{Returns a generator for Dyck words of size \Mpar{n}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the Dyck words}
  \call{\Mtype{nonnegative integer} n}
  \eng{Returns the list of Dyck words of size \Mpar{n}.}
  \call{\Mtype{nonnegative integer} n1, \Mtype{nonnegative integer} n2}%
  \eng{Returns the list of prefix Dyck words, with \Mpar{n1}
    ones and \Mpar{n2} zeroes.}
\end{MMethodDetails}

% \begin{MMethodDetails}{first}
%   \infoEng{first Dyck word}
%   \call{\Mtype{nonnegative integer} n}
%   \eng{Returns the first Dyck word of size \Mpar{n}.}
% \end{MMethodDetails}
    
% \begin{MMethodDetails}{Next}
%   \infoEng{next Dyck word}%
%   \call{\Mtype{Dyck word} w}%
%   \eng{Returns the Dyck word following \Mpar{w} or \Mex{FAIL} if there
%     is none.}
% \end{MMethodDetails}

\begin{MMethodDetails}{toString}
  \infoEng{conversion to string of well balanced parenthesis} %
  \call{\Mtype{Dyck word} w}%
  \eng{Returns the string of well balanced parenthesis corresponding
    to the Dyck word \Mpar{w}, replacing "1" with "(" and "0" with ")". Note
    that the function works even if the word is not well balanced.}%
  \eng{See also the function \Mup{combinat::dyckWords::fromString}}
\end{MMethodDetails}

\begin{MMethodDetails}{fromString}
  \infoEng{conversion from string of well balanced parenthesis}
  \call{\Mtype{string} s}%
  \eng{Returns the Dyck word corresponding to the string of well balanced
    parenthesis \Mpar{s}, replacing "(" with "1" and ")" with "0". Note
    that the function does not check if the string is indeed well balanced.}%
  \eng{See also \Mup{combinat::dyckWords::toString}}
\end{MMethodDetails}

\begin{MMethodDetails}{toNonCrossingPartition}
  \infoEng{Biane bijection to non crossing set partitions} %
  \call{\Mtype{Dyck word} w}%
  \eng{Returns the non-crossing set partition corresponding
    to the Dyck word \Mpar{w} by the Biane bijection.}%
  \eng{\begin{sloppypar}
    See also \Mup{combinat::nonCrossingPartitions} and
    \Mup{combinat::dyckWords::fromNonCrossingPartition}
    \end{sloppypar}}
  \eng{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}
\end{MMethodDetails}

\begin{MMethodDetails}{fromNonCrossingPartition}
  \infoEng{Biane bijection from non-crossing set partitions}
  \call{\Mtype{non crossing set partition} p}%
  \eng{Returns the Dyck word corresponding to the non crossing set
    partition \Mpar{p} by the Biane bijection.}%
  \eng{See also \Mup{combinat::dyckWords::toNonCrossingPartition}}
\end{MMethodDetails}


\begin{MExample}{dw-basic}
  \eng{There are $5$ Dyck words of size $3$:}
  \begin{Mexin}
combinat::dyckWords::count(3)
  \end{Mexin}
  \begin{Mexout}
                               5
  \end{Mexout}

  \eng{Here is the list:}
  \begin{Mexin}
combinat::dyckWords::list(3)
  \end{Mexin}
  \begin{Mexout}
[[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]]
  \end{Mexout}

  \eng{They correspond to the $5$ strings of well-balanced
    parenthesis of length $6$:}
  \begin{Mexin}
map(combinat::dyckWords::list(3), combinat::dyckWords::toString)
  \end{Mexin}
  \begin{Mexout}
      ["((()))", "(()())", "(())()", "()(())", "()()()"]
  \end{Mexout}

  \eng{On the other hand, neither \Mex{[1,0,0,1,1,0]} nor
    \Mex{[1,1,1,1,0,0]} are Dyck words:}
  \begin{Mexin}
combinat::dyckWords::toString([1,0,0,1,1,0]);
combinat::dyckWords::toString([1,1,1,1,0,0])
  \end{Mexin}
  \begin{Mexout}
                           "())(()"

                           "(((())"
  \end{Mexout}
\end{MExample}

\begin{MExample}{dw-isA}
  \eng{In this example we check the type of some Dyck words.}
  \begin{Mexin}
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);
  \end{Mexin}
  \begin{Mexout}
                             TRUE
 
                             TRUE
 
                             FALSE
  \end{Mexout}
  \eng{The list \Mex{[1,0,0,1,1,0]} is not a Dyck word:}
  \begin{Mexin}
combinat::dyckWords::isA([1, 0, 0, 1, 1, 0]); 
combinat::dyckWords::isA([1, 0, 0, 1, 1, 0], 3); 
  \end{Mexin}
  \begin{Mexout}
                             FALSE
 
                             FALSE
  \end{Mexout}
  \eng{The list \Mex{[1,1,1,1,0,0]} is not a Dyck word, but a 
       prefix Dyck word:}
  \begin{Mexin}
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);
  \end{Mexin}
  \begin{Mexout}
                             FALSE
 
                             TRUE
 
                             TRUE
 
                             TRUE
  \end{Mexout}


\end{MExample}

% \eng{When you want to run through the Dyck words of a number, you can
%   generate them one by one to save memory:}
% \begin{Mexin}
% g := combinat::dyckWords::generator(4):
% g(); g(); g(); g(); g(); g()
% \end{Mexin}
% \begin{Mexout}
% \end{Mexout}

% \eng{Typically, this would be used as follows:}
% \begin{Mexin}
% g := combinat::dyckWords::generator(4):
% while (p := g()) <> FAIL do print(p): end:
% \end{Mexin}
% \begin{Mexout}
% \end{Mexout}
% \end{MExample}

\begin{MExample}{dw-string}
  \eng{One can convert a Dyck word to a string of well-balanced
    parenthesis:}
  \begin{Mexin}
combinat::dyckWords::toString([1,1,1,0,1,1,0,0,0,1,0,0,1,1,1,0,0,0,1,0]);
  \end{Mexin}
  \begin{Mexout}
                    "((()(()))())((()))()"
  \end{Mexout}
  \eng{And convert it back:}
  \begin{Mexin}
combinat::dyckWords::fromString("((()(()))())((()))()");
  \end{Mexin}
  \begin{Mexout}
 [1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0]
  \end{Mexout}
\end{MExample}

\begin{MExample}{dw-noncrossingsetpartitions}
  \eng{Dyck words of size $n$ are in bijection with non-crossing set
    partitions of \Mmath{{1, 2, ..., n}}{\{1, 2, \ldots, n\}}. Here
    is the the image of \Mex{[1,0,1,0,1,0]} by the Biane bijection:}
  \begin{Mexin}
combinat::dyckWords::toNonCrossingPartition([1,0,1,1,0,0,1,0])
  \end{Mexin}
  \begin{Mexout}
                      {[1], [4], [2, 3]}
  \end{Mexout}
  \eng{We can reconstruct the original Dyck word:}
  \begin{Mexin}
combinat::dyckWords::fromNonCrossingPartition({[1], [4], [2, 3]})
  \end{Mexin}
  \begin{Mexout}
                   [1, 0, 1, 1, 0, 0, 1, 0]
  \end{Mexout}
  
  \eng{Here is the list of all non-crossing set partitions of
    \Mmath{{1, 2, 3}}{\{1, 2, 3\}}:}
  \begin{Mexin}
map(combinat::dyckWords::list(3),
    combinat::dyckWords::toNonCrossingPartition)
  \end{Mexin}
  \begin{Mexout}
[{[1, 2, 3]}, {[2], [1, 3]}, {[3], [1, 2]}, {[1], [2, 3]},

   {[1], [2], [3]}]
  \end{Mexout}
\end{MExample}

\begin{MBackground}
  \eng{Dyck words are naturally ordered lexicographically.}
  
  \eng{\begin{sloppypar}
    The current implementation of the generator is not optimized,
    and simply uses \Mup{combinat::dyckWords::list}. See the example
    section of \Mup{combinat::integerVectors} for a way of building a
    proper generator for Dyck words.
    \end{sloppypar}}
\end{MBackground}

\MSuperDomain{Dom::BaseDomain}

\begin{MAxioms}
  \Mup{Ax::systemRep}
\end{MAxioms}

\begin{MChanges}
  \version{2.5}%
  \eng[New library]{\Mthis{} is a new library}
\end{MChanges}

\end{Mhelppage}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: main
%%% End: 
