%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Id: decomposableObjects.tex,v 1.1.1.8 2005/01/26 13:42:24 nthiery Exp $
% File:         lib/COMBINAT/DOC/decomposableObjects.tex
% Authors:      Sébastien Cellier <snoteip@yahoo.fr>
%               Nicolas.Thiéry <nthiery@users.sf.net>
% Credits:      Many examples are taken from the documentation of cs 1.5
% Created:      09/06/2002
% Purpose:      Documentation of the library 'combinat::decomposableObjects'
% License:      LGPL
% Language:     English
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{Mhelppage}{decomposableObjects}{S.~Cellier and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{nthiery}{10/2003}{proofread}
\Mproofread{nthiery}{07/2004}{proofread}

%\newcommand{\fr}[1]{} % until french is supported by the MuPAD style file

\begin{MInfo}
  \eng{decomposable combinatorial objects}
\end{MInfo}

% These option declarations influence
% the list of options in stdlib.mdvi!
\MDeclareOption{\Labelled}{Labelled}
\MDeclareOption{\Products}{Products}
\MDeclareOption{\Lazy}{Lazy}
\MDeclareOption{\Holonomic}{Holonomic}
\MDeclareOption{\Naive}{Naive}
% \MDeclareOption{\Cgmp}{C,GMP}
% \MDeclareOption{\Cdpe}{C,DPE}
% \MDeclareOption{\Jtext}{Java,Text}
% \MDeclareOption{\Japplet}{Java,Applet}
% \MDeclareOption{\Jgraphics}{Java,Graphics}
\MDeclareOption{\MT}{MainNonTerminal}
\MDeclareOption{\Alias}{Alias}
\MDeclareOption{\Atom}{Atom}
\MDeclareOption{\Union}{Union}
\MDeclareOption{\Prod}{Prod}
\MDeclareOption{\BoxedProd}{BoxedProd}
\MDeclareOption{\OptTheta}{Theta}
\MDeclareOption{\Int}{Int}
\MDeclareOption{\DivX}{DivX}
\MDeclareOption{\MultX}{MultX}
\MDeclareOption{\OptDelta}{Delta}
\MDeclareOption{\OptEpsilon}{Epsilon}
\MDeclareOption{\Predefined}{Predefined}
\MDeclareOption{\MainTerminal}{MainTerminal}
\MDeclareOption{\Powerset}{Powerset}
\MDeclareOption{\Multiset}{Multiset}
\MDeclareOption{\Cycle}{Cycle}
\MDeclareOption{\Sequence}{Sequence}
\MDeclareOption{\Float}{Float}
\MDeclareOption{\CoeffRing}{CoeffRing}
\MDeclareOption{\Boustrophedonic}{Boustrophedonic}

\begin{todo}
  use the \Alias\ etc. below!
\end{todo}


\begin{MIntro}
  \eng{\begin{sloppypar}
    The library \Mex{\Mthis{}(specification)} provides functions
    for counting, generating, and drawing at random the decomposable
    combinatorial objects defined recursively by
    \Mpar{specification}.
    \end{sloppypar}}
\end{MIntro}

\begin{MDomConst}
  \MCall{specification \Mopt{, Options}}
\end{MDomConst}

\begin{MParameters}
  \param{specification}
  \eng{A combinatorial specification}
\end{MParameters}

\begin{MOptions}
  \option{\Labelled{} = \Mex{b}}
  
  \eng{Selects between labeled or unlabeled combinatorial objects.
    \Mex{b} must be \Mex{TRUE} or \Mex{FALSE}. The default value is
    \Mex{FALSE}. }

  \option{\Products{} = \Mex{Type}}
  
  \eng{Choose the counting algorithm. \Mex{Type} is one of \Naive,
    \Holonomic. The default value is \Holonomic{} for context free
    grammars, and \Naive{} otherwise. See \Mslot{count} for details.}

  \option{\MT{} = \Mex{A}}
  
  \eng{Specifies the main non terminal of the specification. \Mex{A}
    must be a non terminal appearing in the specification. By default,
    the first one (as returned by \Mex{op(specification,[1,1])} is
    used).  This option used to be incorrectly named
    \Mex{MainTerminal}.}

  \option{\Boustrophedonic{} = \Mex{b}}
  
  \eng{Specifies the order in which elements of products are
    generated; see ``background'' section for more details. \Mex{b}
    must be \Mex{TRUE} or \Mex{FALSE}. The default value is
    \Mex{TRUE}. }

  \option{\Float{} = \Mex{b}}
  
  \eng{Specifies whether floating point arithmetic should be used for
    fast approximate counting; see the
    example~\ref{ex-advanced-counting} for details.  \Mex{b} must be
    \Mex{TRUE} or \Mex{FALSE}. The default value is \Mex{FALSE}. }
\end{MOptions}

\MKeywords{combinatorics,decomposable object,partitions,sequence,count,random}

\begin{MDetails}
  \eng{A decomposable combinatorial class is recursively built from
    basic classes using \emph{constructors}. The basic classes are:
    \begin{itemize}
    \item \OptEpsilon\ or \Mex{\OptEpsilon(A)}:\\
      a class containing a single object of size zero, named
      \OptEpsilon{} or \Mex{A}; as a syntactic sugar, a production of
      the form \Mex{A = \OptEpsilon} is rewritten into \Mex{A = \OptEpsilon(A)};
    \item \Atom{} or \Mex{\Atom(A)}:\\
      a class containing a single object of size one, named \Atom{} or
      \Mex{A}; as a syntactic sugar, a production of the form \Mex{A =
        \Atom} is rewritten into \Mex{A = \Atom(A)}; one can also
      specify weights for atoms and epsilons; see the
      example~\ref{ex-advanced-counting} for details;
    \item \Mex{Z}:\\
      this is equivalent to \Mex{\Atom(Z)}, and is provided as a
      syntactic sugar;
    \item \Mex{\Predefined(count\Mopt{, random}\Mopt{, unrank})}:\\
      a class described by the functions \Mex{count}, \Mex{random},
      \Mex{unrank};
    \item \Mex{Domain(class)} or \Mex{class}:\\
      \begin{sloppypar}
      a combinatorial class represented by the \mupad{} domain \Mex{class} (see
      \Mup{Cat::CombinatorialClass}).
      \end{sloppypar}
    \end{itemize}
    The available constructors are:
    \begin{itemize}
    \item \Mex{Union(A, B, ...)}:\\
      the disjoint union of the classes A, B, ...
    \item \Mex{Prod(A, B, ...)}:\\
      the partitional product of the classes A, B, ...
    \item \Mex{BoxedProd(A, B, ...)}:\\
      (for labelled structures) similar to \Prod, but forces
      the smallest label to be on the A side.
    \item \Mex{Sequence(A)}:\\
      all sequences of elements of A;
      A should not contain elements of size zero
    \item \Mex{Multiset(A)}:\\
      all sets of elements of A with repetitions;
      A should not contain elements of size zero
    \item \Mex{Powerset(A)}:\\% or \Mex{SetOf(A)}
      all sets of elements of A without repetitions;
      A should not contain elements of size zero
%%       (beware: starting from \mupad{} 3.0.0, \Mex{Set} is also a
%%       standard \mupad{} domain; please use \Mex{SetOf} instead, or
%%       make sure to protect it with \Mex{hold(Set)}).
    \item \Mex{Cycle(A)}:\\
      all directed cycles of elements of A, including the empty cycle;
      A should not contain elements of size zero
%    \item \Mex{Subst(A,B)}:\\
%      B-objects whose atoms are replaced by A-objects
    \item \Mex{Alias(A)}, \Mex{Alias(A,f)}: an alias to the class
      \Mex{A}, or the image of the class \Mex{A} by the function
      \Mex{f}.
    \end{itemize}
    \begin{sloppypar}
      The constructor \Mex{Sequence} as well as, in the labelled case,
      the constructors \Mex{Powerset}, \Mex{Multiset}, and \Mex{Cycle}
      accept further options \Mex{MinLength}, \Mex{MaxLength}, and
      \Mex{Length} to set length restrictions: for example,
      \Mex{Sequence(A, MinLength=3, MaxLength=5)} represents all the
      sequences of elements of \Mex{A} of length between 3 and 5.
    \end{sloppypar}}
  
  \eng{A combinatorial specification is a list (or set or table) of
    productions of the form \Mex{A = <rhs>}, where \Mex{A} is the name
    of the class being defined, and \Mex{<rhs>} is an expression
    involving elementary classes, constructors and other classes.
    \Mex{A} is called a \emph{non terminal}.  For example, below are
    the specifications of some well-known combinatorial classes:

    Labelling type = 'labelled':\\
    \begin{tabular}{ll}
      \Mex{[A = Prod(Z,Powerset(A))]} &                 non plane trees\\
      \Mex{[B = Union(Z,Prod(B,B))]} &                  plane binary trees\\
      \Mex{[C = Prod(Z,Sequence(C))]} &                 plane general trees\\
      \Mex{[D = Powerset(Cycle(Z))]} &                  permutations in cycle notation\\
      \Mex{[E = Powerset(Cycle(A)), A=Prod(Z,Powerset(A))]} &  functional graphs\\
      \Mex{[F = Powerset(Powerset(Z,MinLength=1))]} &   set partitions\\
      \Mex{[G = Union(Z,Prod(Z,Powerset(G,Length=3)))]} & non plane ternary trees\\
      \Mex{[H = Union(Z,Powerset(H,MinLength=2))]} &    hierarchies\\
      \Mex{[L = Powerset(Powerset(Powerset(Z,MinLength=1),MinLength=1))]} & 3-balanced hierarchies\\
      \Mex{[M = Sequence(Powerset(Z,MinLength=1))]} &   surjections\\
    \end{tabular}
    
    Labelling type = 'unlabelled':\\
    \begin{tabular}{ll}
      \Mex{[A = Multiset(Sequence(Z,MinLength=1))]} &   integer partitions\\
      \Mex{[B = Sequence(Union(Z,Z))]}      &           binary sequences\\
      \Mex{[C = Cycle(Sequence(Z,MinLength=1))]} &      necklaces\\
      \Mex{[D = Prod(Z,Multiset(D))]} &                 rooted unlabelled trees\\
      \Mex{[E = Powerset(Cycle(D)), D=Prod(Z,Powerset(D))]} &  random mappings patterns\\
      \Mex{[F = Union(Z,Multiset(F,Length=2))]} &       nonplane binary trees\\
      \Mex{[G = Union(Z,Multiset(G,Length=3))]} &       nonplane ternary trees\\
      \Mex{[H = Union(Z,Multiset(H,MinLength=2))]} &    unlabelled hierarchies\\
    \end{tabular}
    
    Note: some of the unlabelled specifications above require not yet
    implemented features. }
  
  \eng{A specification is \emph{context free} if it only uses the
    constructors \Mex{Prod} and \Mex{Union}, and those derived from
    them like \Mex{Sequence}. In particular this excludes the
    \Mex{Powerset}, \Mex{Multiset}, and \Mex{Cycle} constructions. Some
    features of this library are only available for context free
    specifications.}

%%   \eng{Different examples of the use of options are available 
%%     Cf.\ examples~\ref{ex-Binary-naive},
%%     \ref{ex-Schroeder-naive} and~\ref{ex-Schroeder-holonomic}.}  
%%   \fr{Différents exemples d'utilisation de ces options sont disponibles 
%%     Cf.\ exemples~examples~\ref{ex-Binary-naive},
%%     \ref{ex-Schroeder-naive} et~\ref{ex-Schroeder-holonomic}.}
  
  \eng{When the specification uses \Mex{Domain(class)}, the system can
    of course only do counting if the provided domain \Mex{class} can,
    and similar wise for \Mex{random}, \Mex{unrank}, \dots}
\end{MDetails}

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

\begin{MMethodDetails}{count}
  \infoEng{number of decomposable objects}
  \call{\Mtype{nonnegative integer} n\Mopt{, A}}%
  \eng{Returns the number of objects of size \Mpar{n} derived by the
    non terminal \Mpar{A} in the specification.}%
  \eng{By default, \Mpar{A} is the main non terminal.}%
  \eng{If \Products{} is set to \Naive{}, the counting is done by
    naive products of generating series; this gives a $O(n^2)$
    complexity (not counting the coefficient growth). Those products
    could be done using a lazy Karatsuba-type algorithm with a
    complexity of \Mex{O(n^{3/2})}; however this is currently only
    partly implemented (\Products{} will be \Lazy{}).}%
  \eng{If \Products{} is set to \Holonomic{}, the system will first
    precompute a linear recurrence between the coefficients of the
    generating series (see \Mslot{recurrenceRelation}), and then use
    it for the counting; this gives a complexity of $O(n)$. This is
    only possible for context free specifications. Also, for very large
    specifications (say more than 100 non terminals), the precomputation
    can become quite expensive; if one is only interested in counting
    for small values of $n$ (say $n\leq 1000$), it may be preferable
    to stick to \Naive{} or \Lazy{} products.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for decomposable objects}
  \call{\Mtype{nonnegative integer} n\Mopt{, A}}%
  \eng{Returns a generator for the objects of size \Mpar{n} derived by
    the non terminal \Mpar{A} in the specification.}%
  \eng{By default, \Mpar{A} is the main non terminal.}
  \eng{Currently, this method is based on \Mslot{unrank}, and only
    works for context free grammars. }%
%  \fr{Renvoie le générateur des objets de taille \Mpar{n} vérifiant la 
%    spécification}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of decomposable objects}
  \call{\Mtype{nonnegative integer} n\Mopt{, A}}%
  \eng{Returns the list of the objects of size \Mpar{n} derived by
    the non terminal \Mpar{A} in the specification.}%
  \eng{By default, \Mpar{A} is the main non terminal.}
  \eng{Currently, this method is based on \Mslot{unrank}, and only
    works for context free grammars. }%
%  \fr{Renvoie tous les objets de taille \Mpar{n} vérifiant la 
%    spécification.}
\end{MMethodDetails}

\begin{MMethodDetails}{unrank}
  \infoEng{unranking of decomposable object}
  \call{\Mtype{nonnegative integer} i, \Mtype{nonnegative integer} n\Mopt{, A}}%
  \eng{Returns the i-th object of size \Mpar{n} derived by the non
    terminal \Mpar{A} in the specification.}%
  \eng{By default, \Mpar{A} is the main non terminal.}%
  \eng{Currently, this method only works for context free grammars;
    algorithm do exists for the other constructions, but are not yet
    implemented. }%
  \eng{The worst case complexity is $O(n \log n)$ with the
    \Boustrophedonic{} order, and $O(n^2)$ otherwise.}
%  \fr{Renvoie le i-ème objet  de taille \Mpar{n} vérifiant la
%    spécification.}
\end{MMethodDetails}

\begin{MMethodDetails}{random}
%  \infoFr{tirage aléatoire d'un objet}
  \infoEng{random object}
  \call{\Mtype{nonnegative integer} n\Mopt{, A}}%
  \eng{Returns a random object of size \Mpar{n} derived by
    the non terminal \Mpar{A} in the specification.}%
  \eng{By default, \Mpar{A} is the main non terminal.}
  \eng{The worst case complexity is $O(n \log n)$ with the
    \Boustrophedonic{} order, and $O(n^2)$ otherwise.}
%  \eng{Returns a random object of size \Mpar{n}}
%  \fr{Renvoie un tirage aléatoire de la spécification de taille \Mpar{n}}
\end{MMethodDetails}

\begin{MMethodDetails}{standardSpecification}
  \infoEng{specification in standard form}
  \call{}%
  \eng{Returns the standard form of the specification; this is an
    equivalent specification which uses only the constructors \Atom,
    \Union, \Prod, \OptTheta, \Int, \OptDelta, \DivX, and \MultX.
    \OptTheta\ is the pointing constructor, \Int\ the formal inverse
    of \OptTheta, and \OptDelta\ is the generalized diagonal.}
  %\fr{Renvoie la forme standard de la spécification.}
\end{MMethodDetails}

\begin{MMethodDetails}{standardSpecificationCount}
  \infoEng{specification in standard form}
  \call{}%
  \eng{Returns a simplified form of the specification in standard form
    which is equivalent for counting purposes.}%
  \eng{This is done by sorting the operands of Prod and Union (the
    operations + and * on generating series are commutative!), erasing
    the names of the singletons and atoms and assigning them with a
    default weight if they do not have one yet. Then, the productions
    that are identical are factored out using Alias. Further
    optimizations would be possible; in particular, productions that
    are recursively equivalent are not detected yet.}
\end{MMethodDetails}

\begin{MMethodDetails}{algebraicEquation}
  \infoEng{algebraic equation for the generating series}
  \call{\Mopt{\Mpar{A}}}%
  \eng{Returns an algebraic equation satisfied by the
    generating series for the non terminal \Mex{A}.}%
  \eng{Computing this algebraic equation is only possible if the
    specification is context free; \Mex{FAIL} is returned if this is
    not the case.}
\end{MMethodDetails}

\begin{MMethodDetails}{recurrenceRelation}
  \infoEng{recurrence relation for the coefficients of the generating series}
  \call{\Mopt{\Mpar{A}}\Mopt{, \Mtype{identifier} u}\Mopt{,
  \Mtype{identifier} u}}%
  \eng{Returns a recurrence relation between the coefficients of the
    generating series for the non terminal \Mex{A}.}%
  \eng{The recurrence relation is given in the form of an expression
    such as \Mex{u(n) - n*u(n-1) - u(n-2)}, it means that the number
    of objects of size \Mex{n} is equal to \Mex{n} times the number of
    objects of size \Mex{n-1} plus the number of objects of size
    \Mex{n-2}. }
  \eng{Computing the recurrence relation is only possible if the
    specification is context free; \Mex{FAIL} is returned if this is
    not the case.}
\end{MMethodDetails}

\begin{MMethodDetails}{generateCode}
  \infoEng{automatic C code generation}
  \call{\Mtype{string} filename}%
  \eng{Generate a \texttt{C} program in the file \Mpar{filename} which
    can be used for efficient counting and random generation of
    objects.}%
  \eng{To compile the program, the \texttt{GMP} library version 4.0 or
    higher is required; aside from this, any \texttt{C} compiler
    should work. Admitting that \Mex{filename} is \texttt{blah.c},
    here is the command line for the \texttt{gcc} compiler:
    \texttt{gcc blah.c -lgmp -o blah}.}%
  \eng{Once compiled, the program can be used completely independently
    from \mupad{} with the command: \texttt{blah n [k seed]}. This
    writes to the standard output \Mex{k} random objects of size
    \Mex{n} (or \Mex{FAIL} if no object of size \Mex{n} exists), one
    per line. If \Mex{k} is \Mex{0}, then the number of objects of
    size \Mex{n} is output instead. A third parameter \Mex{seed} can
    be provided to initialize the \texttt{GMP} random
    generator.}%
  \eng{There are restrictions on the specifications that the \Mex{C}
    program can manage, in particular for complicated use of
    \Mex{Alias}. An error is raised
    if this is the case.}%
  \eng{Currently the counting algorithm uses naive multiplication of
    generating series and whose time complexity is $O(n^2)$, and
    memory complexity $O(n)$, not taking into account the coefficient
    growth. As for the \Mslot{count} method, this could be reduced to
    $O(n)$ for context free grammars and to $O(n^{3/2})$ otherwise.
    The random generation algorithm is of complexity $n \log(n)$.  For
    quasi-uniform random purpose, the counting could be done with
    floating point numbers (or better interval arithmetic), to ensure
    constant time arithmetic operations.  }
\end{MMethodDetails}


% ---------------------------- Examples ------------------------- 

\begin{MExample}{ex-Binary-naive}
  \eng{We create a domain for complete binary trees:} \fr{Cette
    specification est celle des arbres binaires complets}
  \begin{Mexin}
BinaryNaive:=combinat::decomposableObjects({B=Union(Z,Prod(B,B))}):
  \end{Mexin}
  \begin{Mexout}
  \end{Mexout}

  \eng{Standard form of specification}
  %\fr{Forme standard de la spécification}
  \begin{Mexin}
BinaryNaive::standardSpecification()
  \end{Mexin}
  \begin{Mexout}
                 table(
                   Z = Primitive(1, Z),
                   B = Union(Z, NonTerminal1),
                   NonTerminal1 = Prod(B, B)
                 )
  \end{Mexout}

  \eng{The number of binary tree of size 0 to 10}
  \fr{Le nombre d'arbre binaire de taille 0 à 10}
  \begin{Mexin}
BinaryNaive::count(i) $i=0..10
  \end{Mexin}%$
  \begin{Mexout}
          0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862
  \end{Mexout}

  \eng{A random tree of size 1 and size 2}
  \fr{Un arbre aléatoire de taille 1 et 2}

  \begin{Mexin}
BinaryNaive::random(i)$ i=1..2
  \end{Mexin}%$
  \begin{Mexout}
                         Z, Prod(Z, Z)
  \end{Mexout}
  
  \eng{List of all objects of size 4 satisfying the specification}
  \fr{Liste de toutes les objets de taille 4 vérifiant la spécification}
  \begin{Mexin}
BinaryNaive::list(4)
  \end{Mexin}
  \begin{Mexout}
[Prod(Z, Prod(Z, Prod(Z, Z))), Prod(Z, Prod(Prod(Z, Z), Z)),

   Prod(Prod(Z, Prod(Z, Z)), Z), Prod(Prod(Prod(Z, Z), Z), Z),

   Prod(Prod(Z, Z), Prod(Z, Z))]
  \end{Mexout}
\end{MExample}

%> with(gaia):
%> # number of rooted nonplane unlabelled trees of size 100 is:
%> count({D=Prod(Z,Powerset(D))},unlabelled,D,100);
%                  51384328351659326880337136395054298255277970

\begin{MExample}{ex-Schroeder-naive}
  \eng{This specification is the Schroeder tree with Naive product:}
  \fr{Cette sp\'ecification est celle des arbres de Schroeder avec le produit
   na\"\i f}

  \begin{Mexin}
SchroederNaive:=combinat::decomposableObjects(
{B=Union(Z,Prod(Z,B),Prod(Z,B,B))}):
  \end{Mexin}
  \begin{Mexout}
  \end{Mexout}

  \eng{Standard form of specification}
  \fr{Forme standard de la spécification}
  \begin{Mexin}
SchroederNaive::standardSpecification()
  \end{Mexin}
  \begin{Mexout}
          table(
            Z = Primitive(1, Z),
            B = Union(Z, NonTerminal1, NonTerminal4),
            NonTerminal4 = Prod(Z, NonTerminal3),
            NonTerminal3 = Alias(NonTerminal2, op),
            NonTerminal2 = Prod(B, B),
            NonTerminal1 = Prod(Z, B)
          )
  \end{Mexout}

  \eng{The number of Schroeder tree of size 0 to 10}
  \fr{Le nombre d'arbre de Schroeder de taille 0 à 10}
  \begin{Mexin}
SchroederNaive::count(i) $i=0..10
  \end{Mexin}%$
  \begin{Mexout}
            0, 1, 1, 2, 4, 9, 21, 51, 127, 323, 835
  \end{Mexout}

  \eng{A random tree of size 1 and size 2}
  \fr{Un arbre aléatoire de taille 1 et 2}
  \begin{Mexin}
SchroederNaive::random(i)$ i=1..2
  \end{Mexin}%$
  \begin{Mexout}
                         Z, Prod(Z, Z)
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-Schroeder-holonomic}
  \eng{This specification defines the Schroeder trees with Naive and Holonomic 
product:}
  \fr{Cette specification est celle des arbres de Shroeder avec le produit 
Naive et Holonomic:}
  

  \begin{Mexin}
SchroederHolonomic:=combinat::decomposableObjects(
{B=Union(Z,Prod(Z,B),Prod(Z,B,B))},Products=Holonomic):
SchroederNaive:=combinat::decomposableObjects(
{B=Union(Z,Prod(Z,B),Prod(Z,B,B))}):
  \end{Mexin}
  \begin{Mexout}
  \end{Mexout}

  \eng{Time necessary to count the number of Schroeder tree of 
size 500 according to whether you use the holonomic products or not}
  \fr{Temps pour compter le nombre d'arbres de Schroeder de 
taille 500 selon que l'on utilise ou non les produits holonomiques}
  
  \begin{Mvin}{test=false}
time(SchroederNaive::count(500));time(SchroederHolonomic::count(500));
  \end{Mvin}
  \begin{Mvout}{test=false}
                              11340
   
                              30
  \end{Mvout}

  \eng{Time necessary to generate a random Schroeder tree of 
size 500 according to whether you use holonomic products or not}
  \fr{Temps pour générer un arbre aléatoire de Schroeder de 
taille 500 selon que l'on utilise ou non les produits holonomiques}
  \begin{Mvin}{test=false}
time(SchroederNaive::random(500));
time(SchroederHolonomic::random(500));
  \end{Mvin}
  \begin{Mvout}{test=false} 
                              820
 
                              490
  \end{Mvout}
  
\end{MExample}

\begin{MExample}{ex-schroeder-generator}
  \eng{We demonstrate how to use the functions generator and list.}
%  \fr{Voiçi la démonstation de l'utilisation de generator et de list}

  \begin{Mexin}
Shroeder:=combinat::decomposableObjects(
{B=Union(Z,Prod(Z,B),Prod(Z,B,B))}):
  \end{Mexin}
  \begin{Mexout}
  \end{Mexout}
  \begin{Mexin}
Shroeder::count(5)
  \end{Mexin}
  \begin{Mexout}
                               9
  \end{Mexout}
  \eng{All objects of size 5 satisfying the specification}
%  \fr{Toutes les objets de taille 5 vérifiant la spécification}
  \begin{Mexin}
Shroeder::list(5)
  \end{Mexin}
  \begin{Mexout}
[Prod(Z, Prod(Z, Prod(Z, Prod(Z, Z)))),

   Prod(Z, Prod(Z, Prod(Z, Z, Z))),

   Prod(Z, Prod(Z, Z, Prod(Z, Z))),

   Prod(Z, Prod(Z, Prod(Z, Z), Z)),

   Prod(Z, Z, Prod(Z, Prod(Z, Z))), Prod(Z, Z, Prod(Z, Z, Z)),

   Prod(Z, Prod(Z, Prod(Z, Z)), Z), Prod(Z, Prod(Z, Z, Z), Z),

   Prod(Z, Prod(Z, Z), Prod(Z, Z))]
  \end{Mexout}
  \eng{We build and use a generator for those objects:}
%  \fr{Fabrication du générateur}
  \begin{Mexin}
f:=Shroeder::generator(5):
  \end{Mexin}
  \begin{Mexout}
  \end{Mexout}
%  \eng{Uses of generator}
%  \fr{Utilisation du générateur}
  \begin{Mexin}    
f() $ i =0..9
  \end{Mexin}%$
  \begin{Mexout}
Prod(Z, Prod(Z, Prod(Z, Prod(Z, Z)))),

   Prod(Z, Prod(Z, Prod(Z, Z, Z))),

   Prod(Z, Prod(Z, Z, Prod(Z, Z))),

   Prod(Z, Prod(Z, Prod(Z, Z), Z)),

   Prod(Z, Z, Prod(Z, Prod(Z, Z))), Prod(Z, Z, Prod(Z, Z, Z)),

   Prod(Z, Prod(Z, Prod(Z, Z)), Z), Prod(Z, Prod(Z, Z, Z), Z),

   Prod(Z, Prod(Z, Z), Prod(Z, Z)), FAIL
  \end{Mexout}
\end{MExample} 

\begin{MExample}{ex-labeled-type}
  \eng{We create a domain for labeled and unlabeled complete binary trees:}
 % \fr{Nous créons les domaines des arbres binaires complets étiquetés et non 
%étiquetés}
  \begin{Mexin}
BinaryUnlabeled:=combinat::decomposableObjects(
{B=Union(Z,Prod(B,B))},Labelled=FALSE):
BinaryLabeled:=combinat::decomposableObjects(
{B=Union(Z,Prod(B,B))},Labelled=TRUE):
  \end{Mexin}
  \begin{Mexout}
  \end{Mexout}
  \eng{Number of objects of size 0 to 10 satisfying the specification}
  \fr{Nombre de objets de taille 0 à 10 vérifiant la spécification}
\begin{Mexin}
BinaryUnlabeled::count(i)$i=0..10;
BinaryLabeled::count(i)$i=0..10;
  \end{Mexin}
  \begin{Mexout}
          0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862

0, 1, 2, 12, 120, 1680, 30240, 665280, 17297280, 518918400,
 
   17643225600
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-trouble-shooting}
  \eng{\Mwarn{} The grammar is not checked for validity. For example,
    the following grammar describes infinitely many objects of size
    zero (\Mex{Prod(B,B), Prod(B, Prod(B,B)), Prod(B, Prod(B,
      Prod(...)))}).  The recursion formulas for counting are not
    well-founded, and \mupad{} goes into an infinite loop when trying
    to compute the number of objects of size $0$.}
  \begin{Mexin}
loop := combinat::decomposableObjects(
    [A = Prod(B, Union(A, B)),
     B = Epsilon(B)]):
loop::count(0):
  \end{Mexin}
  \begin{Mexout}
Error: Recursive definition [See ?MAXDEPTH];
during evaluation of 'DOM_VAR(0,1)::count_functions[A]'
  \end{Mexout}
  \eng{It would be better to emit a more meaningful error message;
    however, it is non trivial to check automatically whether a
    grammar is well-founded or not. For the moment, please consider
    any weird error message like the one above as a good indicator
    that the grammar might be invalid.}
\end{MExample}

%% > with(gaia):
%% > standardform({A=Sequence(B)},labelled);

%%               {A = Union(Epsilon, T0), T0 = Prod[Seq](B, A)}

%% > standardform({A=Powerset(B)},labelled);

%%  {T1 = Theta(B), T3 = Int(T2), A = Union(Epsilon, T3), T2 = Prod[Powerset](T1, A)}

%% > standardform({A=Cycle(B,card>=2)},unlabelled);

%%    {T11 = Union(T8, T10), T6 = Prod[Seq](B, T4), T8 = Prod[Cyc](T7, T6),

%%        T7 = Theta(B), T4 = Union(Epsilon, T6), T9 = Prod[Cyc](T7, T4),

%%        A = Int(T11), T10 = Delta[Cycle(2)](T9)}


\begin{MExample}{application-balls-and-bars}
  \eng{We use the mechanics of \Mthis{} to present the classical and
    striking ``balls and bars'' model for integer compositions. A
    composition like \Mex{[2,1,3]} can be represented as a string of
    balls and bars by using sequences of balls, separated by bars,
    here: \Mex{ "ooIoIooo"}. Such strings can be described by the
    grammar $BB = Union(o, oBB, oIBB)$. }
  \begin{Mexin}
ballsAndBars :=
combinat::decomposableObjects(
   [
    Ball         = Atom("o"),
    Bar          = Epsilon("I"),
    BB           = Union(Ball,
                         Alias(Prod(Ball, BB),op),
                         Alias(Prod(Ball, Bar, BB),op)
                        ),
    BallsAndBars = Alias(BB, _concat)
   ], MainNonTerminal = BallsAndBars):
  \end{Mexin}
  \eng{There are $2^{n-1}$ balls and bars strings with $n$ balls:}
  \begin{Mexin}
ballsAndBars::count(i) $ i = 1..10
  \end{Mexin} %$
  \begin{Mexout}
             1, 2, 4, 8, 16, 32, 64, 128, 256, 512
  \end{Mexout}
  \eng{This can be seen directly from the recurrence relation:}
  \begin{Mexin}
ballsAndBars::recurrenceRelation()
  \end{Mexin}
  \begin{Mexout}
                       2 u(n - 1) - u(n)
  \end{Mexout}

  \eng{Here are all the compositions of $3$:}
  \begin{Mexin}
ballsAndBars::list(3)
  \end{Mexin}
  \begin{Mexout}
               ["ooo", "ooIo", "oIoo", "oIoIo"]
  \end{Mexout}

\end{MExample}

\begin{MExample}{ex-advanced-counting}
  \eng{It is possible to do weighted enumeration by assigning weights
    to the atoms and epsilons. Then, the result of \Mex{S::count(n)}
    is the sum over each object of size n of the product of the
    weights of its atoms and epsilons.}

  \eng{In theory, it would be possible to use weights in any ring;
    however, this is an experimental feature, and there are some non
    documented restrictions on the rings. Also beware that the
    generating operations like \Mslot{random}, \Mslot{unrank},
    \Mslot{list} and \Mslot{generator} rely on the standard definition
    of \Mslot{count}. So, a domain representing a decomposable
    combinatorial class can't be used simultaneously for advanced
    counting and for generation.}
  
  \eng{As a first application, we count unlabelled ordered trees by
    total number of nodes and number of internal nodes. To achieve
    this, we assign a weight of $1$ to leaves and of $q$ to internal
    nodes:}
  \begin{Mexin}
S :=
combinat::decomposableObjects(
   [T    = Union(Leaf, Prod(InternalNode, Sequence(T, MinLength = 1))),
    Leaf = Atom(Leaf, 1),
    InternalNode = Atom(InternalNode, q)],
   CoeffRing = Dom::ExpressionField()):
  \end{Mexin}
  \begin{Mexout}
  \end{Mexout}
  \eng{The \CoeffRing{} option specifies that the recurrence relation
    precomputations should take place in \Mex{Dom::ExpressionField()}.
    Now, \Mex{S::count(n)} computes the generating series by number of
    internal nodes of the trees with $n$ nodes altogether:}
  \begin{Mexin}
expand(S::count(4))
  \end{Mexin}
  \begin{Mexout}
                          3      2
                         q  + 3 q  + q
  \end{Mexout}
  \eng{This means that, among the trees on $4$ nodes, one has a single
    internal node, three have two internal nodes, and one has three
    internal nodes.}
  
  \eng{Another application of this feature is for doing approximate
    counting. To this end, we redefine the previous domain, but this
    time with a weight of $1.0$:}
  \begin{Mexin}
S :=
combinat::decomposableObjects(
   [T    = Union(Leaf, Prod(InternalNode, Sequence(T, MinLength = 1))),
    Leaf = Atom(Leaf, 1.0),
    InternalNode = Atom(InternalNode, 1.0)],
   Products=Naive):
  \end{Mexin}
  \begin{Mexout}
  \end{Mexout}
  \eng{Now, count returns a floating point approximation of the number
    of objects having a given size:}
  \begin{Mexin}
[S::count(i) $ i = 0..10]
  \end{Mexin}
  \begin{Mexout}
[0, 1.0, 1.0, 2.0, 5.0, 14.0, 42.0, 132.0, 429.0, 1430.0,

   4862.0]
  \end{Mexout}
  \begin{Mexin}
S::count(501)
  \end{Mexin} %$
  \begin{Mexout}
                        5.394974869e296
  \end{Mexout}
  \eng{The bonus is that approximate counting is much faster, as there
    is no coefficient growth. However, in order to use the fast
    holonomic counting method, it is safer to use exact arithmetic for
    precomputing the recurrence relation between, and only then to
    switch to approximate counting. This is what we do now: }
  \begin{Mexin}
  S :=
combinat::decomposableObjects(
   [T    = Union(Leaf, Prod(InternalNode, Sequence(T, MinLength = 1))),
    Leaf = Atom(Leaf, 1.0, 1),
    InternalNode = Atom(InternalNode, 1.0, 1)]):
  \end{Mexin}
  \eng{Note that the nodes now have two weights: one for approximate
    computations, and the other for exact computations. Of course
    those two weights should be coherent. Here is the recurrence
    relation obtained by the precomputation:}
  \begin{Mexin}
S::recurrenceRelation()
  \end{Mexin}
  \begin{Mexout}
             4 n u(n) - u(n + 1) (n + 1) - 2 u(n)
  \end{Mexout}
  \eng{Now, one can compute quite large values:}
  \begin{Mvin}{test=false}
S::count(20000)
  \end{Mvin}
  \begin{Mvout}{test=false}
                       7.900503708e12033
  \end{Mvout}
  \eng{Alternatively, one can simply use the \Float{} which does
    exactly this:}
  \begin{Mexin}
S :=
combinat::decomposableObjects(
   [T    = Union(Leaf, Prod(InternalNode, Sequence(T, MinLength = 1))),
    Leaf = Atom(Leaf),
    InternalNode = Atom(InternalNode)],
   Float):
[S::count(i) $ i = 0..10]
  \end{Mexin} %$
  \begin{Mexout}
[0, 1.0, 1.0, 2.0, 5.0, 14.0, 42.0, 132.0, 429.0, 1430.0,

   4862.0]
  \end{Mexout}
  
  \eng{A possible extension would be to allow the constructors like
    \Prod to apply any transformation on the weights of their
    operands. A typical application of this is for computing the
    generating series of binary trees of a given size with respect to
    their maximal depth.}
\end{MExample}

\begin{MBackground}
  \eng{Not all functionalities (\Mex{count}, \Mex{random},
    \Mex{unrank}, \Mex{generator}, \Mex{list}) are available for all
    constructors; some restrictions are documented above;
    otherwise, the system should emit an error if such a non available
    functionality is called.}
    
  \eng{In some cases, there is no known reasonable algorithm: this
    includes mainly unranking and uniform random generation of
    unlabelled \Mex{Cycles}, as well as random generation of labelled
    \Mex{Powerset(A)} without knowing how to unrank elements of
    \Mex{A}. Beware that the currently implemented random generation
    of unlabelled \Mex{Cycles} is not uniform; furthermore, randomly
    generated unlabelled \Mex{Cycles} and \Mex{Sets} are not
    normalized!

    % Xavier, check this: there is no known algorithm for
    % unranking boxed products with worst case complexity O(n log n)
    % at least our current implementation does not achieve this complexity
  }
  
  \eng{In most cases however, the functionalities are just not yet
    implemented. This library could also be extended and generalized
    in many other ways. Please contact the authors if you need some
    missing functionalities for your applications.  Help would also be
    very welcome.}

  \eng{The \Boustrophedonic{} option specifies the order in which
    elements of products are generated. To be specific, the objects of
    size $n$ of a product \Mex{\Prod(A,B)} are built from objects of
    \Mex{A} of size $k$ and objects of \Mex{B} of size $n-k$, for $k$
    in $\{1,\dots,n\}$. The \Boustrophedonic{} option controls in
    which order $k$ runs through $\{1,\dots,n\}$. If it is set to
    false, the straightforward order $k=1..n$ is used.  Otherwise, the
    somewhat less natural order $k=1,n,2,n-2,\dots$ is used; it
    happens that this reduces the worst case complexity of the
    unranking and random generation operations from $O(n^2)$ to
    $O(n\log n)$! }
    
  \eng{This library has been adapted from the \texttt{CS} library for
    \mupad{} 1.4 from Sylvie Corteel, Alain Denise, Isabelle Dutour,
    Frédéric Sarron and Paul Zimmermann. Parts of the documentation
    come from the \texttt{GAIA} package (ancestor of
    \texttt{combstruct}) by Paul Zimmermann.}
  
  \eng{References:
    \begin{itemize}
    \item Flajolet, Philippe and Zimmermann, Paul and Van Cutsem,
      Bernard, A calculus for the random generation of labelled
      combinatorial structures, Theoretical Computer Science, 1994,
      132, 1-2, pp.\ 1--35.
    \item Denise, Alain and Dutour, Isabelle and Zimmermann, Paul, CS:
      a MuPAD package for Counting and Randomly Generating
      Combinatorial Structures, Proceedings of FPSAC'98, 1998, pp.\
      195--204.
    \item Conrado Martinez and Xavier Molinero, Generic Algorithm for
      the Generation of Combinatorial Objects, 2003.

    \item ...
    \end{itemize}}
  
  \eng{The specifications used by this library are in good parts
    compatible with those from the \texttt{combstruct} package for
    \texttt{Maple}. There are some differences though, in order to
    ensure the coherence with the rest of the \mupad{} library: the
    constructor names \Mex{Powerset} and \Mex{Multiset} are used
    instead of respectively \Mex{PowerSet} and \Mex{Set}; furthermore,
    cardinality restrictions are stated as \Mex{MinLength=3} instead
    of \Mex{card>=3}; finally, the \Mex{Cycle} construction includes
    the empty cycle. If needed, it would be straightforward to write a
    converter.}
\end{MBackground}

\MSuperDomain{Dom::BaseDomain}
 
\begin{MAxioms}
  \Mup{Ax::systemRep}
\end{MAxioms}

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

\end{Mhelppage}

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