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

\begin{MInfo}
  \eng{non crossing set partitions}
\end{MInfo}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for non crossing set
    partitions.}
\end{MIntro}

\MKeywords{combinatorics, non crossing set partition}

\begin{MDetails}
  \eng{A \emph{non crossing set partition} of \Mmath{{1, 2, ...,
        n}}{\{1, 2, \ldots, n\}} is a partition $p$ of the set
    \Mmath{{1, 2, ..., n}}{\{1, 2, \ldots, n\}} such that there is no
    $x,y$ in one part of $p$ and $z,t$ in another part of $p$ with
    $x<z<y<t$. For example, \Mex{{[1,3,7], [2], [4,5], [6], [8,9]}} is a
    non crossing set partition, but \Mex{{[1,3], [2,4]}} is not (take
    \Mex{x=1, y=3, z=2, t=4}).}
  
  \eng{A non crossing set partition of \Mmath{{1, 2, ..., n}}{\{1, 2,
      \ldots, n\}} is represented as a set of lists. Each list
    represents a part of the partition, with its elements in
    increasing order.}
    
  \eng{\begin{sloppypar}
    Non crossing set partitions are in bijection with Dyck words
    (library \Mup{combinat::dyckWords}), and many other discrete
    classes.
    \end{sloppypar}}
\end{MDetails}

\begin{MCategories}
\Mup{Cat::CombinatorialClass}
\end{MCategories}

\begin{MDomEntries}
  \MDomEntry{domtype}
  \eng{The \mupad\ domain used to represent non crossing set partitions: \Mup{DOM_SET}}
\end{MDomEntries}

\begin{MMethodDetails}{count}
  \infoEng{number of non crossing set partitions}%
  \call{\Mtype{nonnegative integer} n}%
  \eng{Returns the number of non crossing set  partitions of size 
       \Mpar{n}.}
\end{MMethodDetails}
 
\begin{MMethodDetails}{generator}
  \infoEng{generator for non crossing set partitions}%
  \call{\Mtype{nonnegative integer} n}%
  \eng{Returns a generator for the non crossing set partitions of 
       size \Mpar{n}.}
\end{MMethodDetails}
 
\begin{MMethodDetails}{list}
  \infoEng{list of the non crossing set partitions}%
  \call{\Mtype{nonnegative integer} n}%
  \eng{Returns the list of the non crossing set partitions of 
       size \Mpar{n}.}
\end{MMethodDetails}

\begin{MExample}{ex-basic}
  \eng{There are $14$ non crossing set partitions of size $4$:}
  \begin{Mexin}
combinat::nonCrossingPartitions::count(4)
  \end{Mexin}
  \begin{Mexout}
                              14
  \end{Mexout}
  \eng{Here is the list:}
  \begin{Mexin}
combinat::nonCrossingPartitions::list(4)
  \end{Mexin}
  \begin{Mexout}
[{[1], [2], [3], [4]}, {[1], [2], [3, 4]}, {[1], [4], [2, 3]},
 
   {[1], [3], [2, 4]}, {[1], [2, 3, 4]}, {[3], [4], [1, 2]},
 
   {[1, 2], [3, 4]}, {[2], [4], [1, 3]}, {[4], [1, 2, 3]},
 
   {[2], [3], [1, 4]}, {[2], [1, 3, 4]}, {[1, 4], [2, 3]},
 
   {[3], [1, 2, 4]}, {[1, 2, 3, 4]}]
  \end{Mexout}
  \eng{To generate non crossing set partitions of a given size:}
  \begin{Mexin}
g:= combinat::nonCrossingPartitions::generator(3):
g(); g(); g(); g(); g(); g()
  \end{Mexin}
  \begin{Mexout}
                        {[1], [2], [3]}
 
                         {[1], [2, 3]}
 
                         {[3], [1, 2]}
 
                         {[2], [1, 3]}
 
                          {[1, 2, 3]}
 
                             FAIL
  \end{Mexout}
  \eng{Typically, this would be used as follows:}
  \begin{Mexin}
g := combinat::nonCrossingPartitions::generator(3):
while (p := g()) <> FAIL do print(p): end:
  \end{Mexin}
  \begin{Mexout}
                        {[1], [2], [3]}

                         {[1], [2, 3]}

                         {[3], [1, 2]}

                         {[2], [1, 3]}

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

\begin{MExample}{ex-dyck}
  \eng{Non crossing set partitions implements the Biane bijection with 
       Dyck words.}
  \begin{Mexin}
combinat::dyckWords::count(i) $ i = 1..6;
combinat::nonCrossingPartitions::count(i) $ i = 1..6 
  \end{Mexin}
  \begin{Mexout}
                     1, 2, 5, 14, 42, 132

                     1, 2, 5, 14, 42, 132
  \end{Mexout}

  \eng{And here is a little list comparation:}
  \begin{Mexin}
map(combinat::dyckWords::list(3),
    combinat::dyckWords::toNonCrossingPartition);
combinat::nonCrossingPartitions::list(3)
  \end{Mexin}
  \begin{Mexout}
[{[1, 2, 3]}, {[2], [1, 3]}, {[3], [1, 2]}, {[1], [2, 3]},
 
   {[1], [2], [3]}]
 
[{[1], [2], [3]}, {[1], [2, 3]}, {[3], [1, 2]}, {[2], [1, 3]},
 
   {[1, 2, 3]}]
  \end{Mexout}
\end{MExample}

\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: 
