\section{A guided tour through MuPAD-Combinat}

\Mnode{guidedTour}
\label{guidedTour}

\eng{The main purpose of this package is to provide tools for
  manipulating combinatorial (Hopf) algebras. To setup the stage, we
  start this guided tour by presenting a few sample computations with
  two examples of such algebras. Then, we proceed by illustrating with
  many examples the predefined combinatorial objects and how to define
  new ones and the predefined combinatorial algebras and how to define
  new ones. We conclude this tour by a summary of the current
  features.}

\subsection{Two examples of combinatorial algebras}

\eng{In this tour we assume that the up-to-date \Mex{Combinat} package has
  been loaded into \mupad. Depending on your installation you may have to
  enter a command such as \Mex{package("Combinat"):} or \Mex{package("."):}
  depending on your installation.}

\eng{We define a shortcut for the algebra of symmetric
  functions~\cite{MacDonald.SF.1995}:}
  \begin{Mexin}
S := examples::SymmetricFunctions():
  \end{Mexin}
  \begin{Mvout}{hide=true}
  \end{Mvout}
\eng{We consider the three first elementary symmetric polynomials in
  the variables \Mex{\{x1,...,x6\}}:}
  \begin{Mexin}
alphabet := [ x1, x2, x3, x4, x5, x6]:
e1 := expand(S::e([1])(alphabet));
  \end{Mexin}
%$
  \begin{Mexout}
                  x1 + x2 + x3 + x4 + x5 + x6
  \end{Mexout}
  \begin{Mexin}
e2 := expand(S::e([2])(alphabet));
  \end{Mexin}
  \begin{Mexout}
x1 x2 + x1 x3 + x1 x4 + x2 x3 + x1 x5 + x2 x4 + x1 x6 +

   x2 x5 + x3 x4 + x2 x6 + x3 x5 + x3 x6 + x4 x5 + x4 x6 +

   x5 x6
  \end{Mexout}
  \begin{Mexin}
e3 := expand(S::e([3])(alphabet))
  \end{Mexin}
  \begin{Mexout}
x1 x2 x3 + x1 x2 x4 + x1 x2 x5 + x1 x3 x4 + x1 x2 x6 +

   x1 x3 x5 + x2 x3 x4 + x1 x3 x6 + x1 x4 x5 + x2 x3 x5 +

   x1 x4 x6 + x2 x3 x6 + x2 x4 x5 + x1 x5 x6 + x2 x4 x6 +

   x3 x4 x5 + x2 x5 x6 + x3 x4 x6 + x3 x5 x6 + x4 x5 x6
\end{Mexout}
\eng{As one can see, the system distinguishes between abstract (or
  ``symbolic'') symmetric functions such as \Mex{S::e([3])}, and the
  expansion of them as symmetric polynomials on the alphabet, stored
  here in variables such as \Mex{e3}. The call
  \Mex{expand(f(alphabet))} for an abstract symmetric function \Mex{f}
  actually expands the corresponding symmetric polynomial over the
  alphabet.
  
  Computing the product of two such symmetric polynomials yields a huge
  polynomial which is not quite practical to manipulate:}
\begin{Mvin}{test=false}
  expand(e2*e3)
\end{Mvin}
\begin{Mvout}{test=false}
10 x1 x2 x3 x4 x5 + 10 x1 x2 x3 x4 x6 + 10 x1 x2 x3 x5 x6 +

   10 x1 x2 x4 x5 x6 + 10 x1 x3 x4 x5 x6 + 10 x2 x3 x4 x5 x6 +

                2
   3 x1 x2 x3 x4  + ... (one page of output)

        2   2
   x1 x2  x3  + ... (another page of output)
\end{Mvout}
\eng{Instead, if we use the symmetries, the previous product can be
  expressed as compactly as:}
\begin{Mexin}
  S::m( S::e([2]) * S::e([3]) );
\end{Mexin}
\begin{Mexout}
      10 m[1, 1, 1, 1, 1] + 3 m[2, 1, 1, 1] + m[2, 2, 1]
\end{Mexout}
\eng{Here, \Mex{m[2, 1, 1, 1]} denotes the monomial symmetric function
  $m_{2,1,1,1}$ obtained by summing all the monomials with one
  variable elevated to the power $2$ and three variables to the power
  $1$. The product has been calculated at the level of abstract
  symmetric functions without expanding the polynomials, which is much
  faster and requires substantially less memory.}

\eng{Hence, symmetric functions provide a typical example of
  \emph{combinatorial algebra} whose bases are indexed by
  combinatorial objects (partitions), and where we want to compute
  efficiently.}

\eng{As another typical example, we are currently
  working~\cite{Hivert_Novelli_Thibon.PBT.2002,Hivert_Novelli_Thibon.PBT.2003}
  on the so-called Loday-Ronco algebra~\cite{Loday_Ronco.1998}, which
  is in particular of interest for theoretical
  physicists~\cite{Brouder_Frabetti.2001,Foissy.2001.Thesis}.  It is
  implemented as a combinatorial algebra having binary trees as
  basis. Here we use computation in the fundamental basis denoted by
  \Mex{p}}.
  \begin{Mexin}
LRA := examples::LodayRoncoAlgebra():
  \end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}

  \eng{For example, take the two following trees:}
  \begin{Mexin}
t1 := LRA::p(combinat::binaryTrees::unrank(6, 4))
  \end{Mexin}
  \begin{Mexout}
                           p/  o   \
                            | / \  |
                            \    \ /
  \end{Mexout}
  \begin{Mexin}
t2 := LRA::p(combinat::binaryTrees::unrank(26, 5))
  \end{Mexin}
  \begin{Mexout}
                           p/   o  \
                            |  / \ |
                            \ /\   /
  \end{Mexout}
  \eng{Technically, \Mex{combinat::binaryTrees::unrank(k,n)} returns
    the $k$-th tree with $n$ nodes, while \Mex{LRA::p(t)} returns the
    basis element of LRA::p indexed by $t$.}

  \eng{You can make a formal linear combination of \Mex{t1} and
  \Mex{t2}:}
  \begin{Mexin}
2*t2 + 3/4*t1
  \end{Mexin}
  \begin{Mexout}
                  2 p/   o  \ + 3/4 p/  o   \
                     |  / \ |        | / \  |
                     \ /\   /        \    \ /
  \end{Mexout}
  \eng{or take their product:}
  \begin{Mexin}
t2*t1
  \end{Mexin}%
  \begin{Mexout}
p/   o     \ + p/   o    \ + p/    o   \ + p/   o    \ +
 |  / \    |    |  / \   |    |   / \  |    |  / \   |
 | /\  \   |    | /\ /\  |    |  /\  \ |    | /\ /\  |
 |     /\  |    \    \ \ /    \ /\ \   /    \   /  \ /
 \       \ /

   p/    o   \ + p/     o   \
    |   / \  |    |    / \  |
    |  /\  \ |    |   /   \ |
    \ /\/    /    |  /\     |
                  \ /\      /
  \end{Mexout}
  \eng{Here is a more complicated product in this algebra:} 
  \begin{Mexin}
(2*t2 + 3/4*t1) * t2
  \end{Mexin}
  \begin{Mvout}{test=false}
3/4 p/  o     \ + 3/4 p/  o    \ + 3/4 p/  o   \ +
     | / \    |        | / \   |        | / \  |
     |    \   |        |    \  |        |  / \ |
     |     \  |        |    /\ |        |  \   |
     |     /\ |        |    \  |        |   \  |
     \    /\  /        \    /\ /        \   /\ /
  \end{Mvout}
\newpage
\enlargethispage*{4\baselineskip}
%\hspace{-2cm}
  \begin{Mvout}{test=false}
   3/4 p/   o   \ + 3/4 p/  o    \ + 3/4 p/  o   \ +
        |  /  \ |        | / \   |        | / \  |
        | /\    |        |    \  |        |   /\ |
        |   \   |        |    /\ |        |   \  |
        |    \  |        |   /\  |        |   /\ |
        \    /\ /        \   \   /        \   \  /

   3/4 p/   o  \ + 3/4 p/  o   \ + 3/4 p/   o  \ +
        |  / \ |        | / \  |        |  / \ |
        | /\   |        |   /\ |        | /\   |
        |   \  |        |  /\  |        |  /\  |
        |   /\ |        |  \   |        |  \   |
        \   \  /        \   \  /        \   \  /

   3/4 p/    o  \ + 3/4 p/  o    \ + 3/4 p/  o   \ +
        |   / \ |        | / \   |        | / \  |
        |  / \  |        |    \  |        |   /\ |
        | /\    |        |    /\ |        |   \  |
        |   \   |        |   /\  |        |   /\ |
        \    \  /        \  /    /        \  /   /

   3/4 p/   o  \ + 3/4 p/  o   \ + 3/4 p/   o  \ +
        |  / \ |        | / \  |        |  / \ |
        | /\   |        |   /\ |        | /\   |
        |   \  |        |  /\  |        |  /\  |
        |   /\ |        |  \   |        |  \   |
        \  /   /        \  /   /        \  /   /

   3/4 p/    o  \ + 3/4 p/  o   \ + 3/4 p/   o  \ +
        |   / \ |        | / \  |        |  / \ |
        |  /\   |        |   /\ |        | /\   |
        | /\    |        |  /\  |        |  /\  |
        |   \   |        | /    |        | /    |
        \   /   /        \ \    /        \ \    /

   3/4 p/    o  \ + 3/4 p/     o  \ + 2 p/   o    \ +
        |   / \ |        |    / \ |      |  / \   |
        |  /\   |        |   /\   |      | /\  \  |
        | /\    |        |  /     |      |     /\ |
        |  /    |        | /\     |      \    /\  /
        \  \    /        \   \    /

   2 p/   o   \ + 2 p/    o  \ + 2 p/   o   \ + 2 p/    o  \ +
      |  / \  |      |   / \ |      |  / \  |      |   / \ |
      | /\ /\ |      |  /\   |      | /\ /\ |      |  /\   |
      |    \  |      | /\ \  |      |   /\  |      | /\/\  |
      \    /\ /      \    /\ /      \   \   /      \   \   /
  \end{Mvout}
\clearpage
  \begin{Mvout}{test=false}
   2 p/     o  \ + 2 p/   o   \ + 2 p/    o  \ +
      |    / \ |      |  / \  |      |   / \ |
      |   /\   |      | /\ /\ |      |  / \  |
      |  /\    |      |   /\  |      | /\ /\ |
      \ /\ \   /      \  /    /      \   /   /

   2 p/     o  \ + 2 p/      o  \
      |    / \ |      |     / \ |
      |   /\   |      |    /\   |
      |  /\    |      |   /     |
      \ /\/    /      |  /\     |
                      \ /\      /
  \end{Mvout}

\subsection{MuPAD-Combinat, step by step}

% List of the technical difficulties encountered by Alessandra:
%  grammar, nops, parametrized domain, combinatorial class
% Sergei has also some problems with the word grammar. 

\eng{We now describe in more detail how all of this works. In the
  following, we assume that the package \texttt{MuPAD-Combinat} has
  been loaded into \mupad{}. We also assume that the
  reader is somewhat familiar with the \mupad{}
  syntax\ifincludeExercises, and some of the exercises requires
  acquaintance with more advanced features of \mupad{} like domain
  programming.\fi{} We refer to the \mupad{}
  \Mhref[tutorium,firstpage]{tutorial} for details.  Technicalities
  can be safely ignored in a first reading; they will be better
  understood after the explanations in the \Mhref[index,design]{design
    notes}}.

% Don't remove the * in \subsubsection*; otherwise, the scope of the
% export above in the testsuite will just end here.
% Florent : I've put them back for compiling, according to
% Volker advice. 
\subsubsection{Using predefined combinatorial functions and classes}
\eng{For shortening the notations, we export the library \Mex{combinat}:}
\begin{Mexin}
  export(combinat):
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}

\eng{We start by some sample applications at random. We compute the
  first terms of the famous Catalan sequence, we generate the
  Cartesian product of three lists, we compute all permutations of the
  numbers $1, 2, 3$, and we ask for all sub-words of the word \Mex{[a,
    b, c, d]}:}
\begin{Mexin}
catalan(i) $ i = 0..10
\end{Mexin}
% $
\begin{Mexout}
        1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796
\end{Mexout}
\begin{Mexin}
cartesianProduct::list([1,2,3],[a,b],[i,ii,iii])
\end{Mexin}
\begin{Mexout}
[[1, a, i], [1, a, ii], [1, a, iii], [1, b, i], [1, b, ii],

   [1, b, iii], [2, a, i], [2, a, ii], [2, a, iii], [2, b, i],

   [2, b, ii], [2, b, iii], [3, a, i], [3, a, ii],

   [3, a, iii], [3, b, i], [3, b, ii], [3, b, iii]]
\end{Mexout}
\begin{Mexin}
permutations::list([1, 2, 3])
\end{Mexin}
\begin{Mexout}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2],

   [3, 2, 1]]
\end{Mexout}
\begin{Mexin}
subwords::list([a,b,c,d])
\end{Mexin}
\begin{Mexout}
[[], [a], [b], [c], [d], [a, b], [a, c], [a, d], [b, c],

   [b, d], [c, d], [a, b, c], [a, b, d], [a, c, d], [b, c, d],

   [a, b, c, d]]
\end{Mexout}

\eng{
  \begin{sloppypar}
    We turn now to various combinatorial classes. In short, a
    \emph{combinatorial class} is a set of related combinatorial objects,
    like the set of all integer partitions. For every such classes, there
    is a sub-library of \Mex{combinat}.  We can use the library
    \Mup{combinat::partitions} to list all the integer partitions of
    $5$:
  \end{sloppypar}
}
\begin{Mexin}
partitions::list(5)
\end{Mexin}
\begin{Mexout}
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1],

   [1, 1, 1, 1, 1]]
\end{Mexout}
\eng{Let us draw the partition \Mex{[3,2]} using boxes
  (French or Cartesian notation):}
\begin{Mexin}
partitions::printPretty([3, 2])
\end{Mexin}
\begin{Mexout}
                         +---+---+
                         |   |   |
                         +---+---+---+
                         |   |   |   |
                         +---+---+---+
\end{Mexout}
\eng{We can fill those boxes with the numbers \Mex{1,2,3,4,5} so that
  the numbers are increasing along rows and columns to obtain
  so-called \emph{standard tableaux}. Here are all the standard
  tableaux of shape \Mex{[3,2]}:}
\begin{Mexin}
map(tableaux::list([3, 2]), tableaux::printPretty)
\end{Mexin}
\begin{Mexout}
-- +---+---+      +---+---+      +---+---+      +---+---+
|  | 4 | 5 |      | 3 | 5 |      | 2 | 5 |      | 3 | 4 |
|  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
|  | 1 | 2 | 3 |, | 1 | 2 | 4 |, | 1 | 3 | 4 |, | 1 | 2 | 5 |,
-- +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

   +---+---+     --
   | 2 | 4 |      |
   +---+---+---+  |
   | 1 | 3 | 5 |  |
   +---+---+---+ --
\end{Mexout}

\eng{Ordered trees are another typical combinatorial class. Here are
  all the trees on four nodes:}
\begin{Mexin}
trees::list(4)
\end{Mexin}
\begin{Mexout}
                  --  o ,  o ,  o ,  o , o --
                  |  /|\  / \  / \   |   |  |
                  |         |  |    / \  |  |
                  --                     | --
\end{Mexout}
\eng{and here are some more trees:}
\begin{Mexin}
trees::list(6)
\end{Mexin}
\begin{Mexout}
--   o  ,   o  ,   o  ,  o  ,  o ,   o  ,  o ,   o  ,  o ,
|  //|\\  // \\  // \\  /|\   /|\  // \\  /|\  / | \  /|\
|             |     |     /\    |   |      ||   / \    |
|                               |                      |
|
--

    o  ,  o  ,  o  ,  o  ,  o ,   o  ,  o ,  o ,  o  ,  o ,
   / \   / \   / \   / \   / \  // \\  /|\  /|\  / \   / \
    /|\    /\    /\    |     |  |      | |  ||   | /\  | |
            |    |    / \    |                           |
                             |

     o ,   o ,  o ,  o ,   o ,   o ,   o ,   o ,  o ,   o  ,
    /|\   / \  /|\  / \   / \   / \   / \   / \  / \    |
   /\    /\ |  |    | |  /|\   /\    /\     |    |    // \\
               |    |           |    |     / \   |
                                                 |

    o ,  o ,  o  ,  o ,  o ,  o ,   o ,  o ,  o ,  o ,  o ,
    |    |    |     |    |    |     |    |    |    |    |
   /|\  /|\  / \   / \  /|\  / \   / \  / \   |    |    |
     |   |     /\    |  |    | |  /\    |    /|\  / \  / \
                     |                  |           |  |

    o , o --
    |   |  |
    |   |  |
    |   |  |
   / \  |  |
        | --
\end{Mexout}

\eng{All the sub-libraries of \Mup{combinat} share a standardized
  interface.  Let us look in more detail at the library
  \Mup{combinat::partitions}.  We can count partitions:}
\begin{Mexin}
partitions::count(i) $ i = 0..10
\end{Mexin}
% $
\begin{Mexout}
             1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42
\end{Mexout}
\eng{list them under some extra conditions (here we list the partitions
  of $5$ whose length is between $2$ and $3$):}
\begin{Mexin}
partitions::list(5, MinLength = 2, MaxLength = 3);
\end{Mexin}
\begin{Mexout}
            [[4, 1], [3, 2], [3, 1, 1], [2, 2, 1]]
\end{Mexout}
\eng{or compare them (lexicographically):}
\begin{Mexin}
bool(partitions::_less([3, 1], [2, 2]))
\end{Mexin}
\begin{Mexout}
                             FALSE
\end{Mexout}
\eng{An important feature of \mupadcombinat{} are the so-called
  \emph{generators}, which allow programs to run through huge lists of
  combinatorial objects without expanding the full lists into memory.
  Technically, a generator is a function \Mex{g} such that each call
  \Mex{g()} returns either a new object, or FAIL if no more objects
  are available. Let us build a generator for the partitions of $4$:}
\begin{Mexin}
g := partitions::generator(4):
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
\eng{Here is the first partition of $4$:}
\begin{Mexin}
g()
\end{Mexin}
\begin{Mexout}
                              [4]
\end{Mexout}
\eng{Here is the second partition of $4$:}
\begin{Mexin}
g()
\end{Mexin}
\begin{Mexout}
                            [3, 1]
\end{Mexout}
\eng{And here are the remaining ones:}
\begin{Mexin}
g(), g(), g(), g()
\end{Mexin}
\begin{Mexout}
             [2, 2], [2, 1, 1], [1, 1, 1, 1], FAIL
\end{Mexout}

Generators come in handy when you want to work with the $53174$
partitions of $42$:
\begin{Mexin}
g := partitions::generator(42):
g(), g(), g(), g(), g(), g()
\end{Mexin}
\begin{Mexout}
    [42], [41, 1], [40, 2], [40, 1, 1], [39, 3], [39, 2, 1]
\end{Mexout}
\eng{Most of the sub-libraries of \Mup{combinat} provide such generators.}

\eng{Whenever possible (i.e. when it does not harm the computational
  complexity), we focus on providing the user with generic tools that
  cover many kinds of applications. For example, the libraries for
  partitions, integer vectors, and compositions share a very similar
  interface:}
\begin{Mexin}
integerVectors::list(10, 3, MinPart = 2, MaxPart = 5,
                            Inner = [2, 4, 2])
\end{Mexin}
\eng{(Note: \Mex{Inner = [2, 4, 2]} means that the three parts should
  be respectively at least \Mex{2}, \Mex{4}, and \Mex{2}).}
\begin{Mexout}
    [[4, 4, 2], [3, 5, 2], [3, 4, 3], [2, 5, 3], [2, 4, 4]]
\end{Mexout}
\begin{Mexin}
compositions::list(5, MaxPart = 3, MinPart = 2,
                      MinLength = 2, MaxLength = 3)
\end{Mexin}
\begin{Mexout}
                       [[3, 2], [2, 3]]
\end{Mexout}
\begin{Mexin}
partitions::list(5, MaxSlope = -1)
\end{Mexin}
\begin{Mexout}
                     [[5], [4, 1], [3, 2]]
\end{Mexout}
\eng{%
  \begin{sloppypar}
    \noindent Those libraries actually use internally the same computational
    engine \Mup{combinat::integerListsLexTools}:
  \end{sloppypar}
}
\begin{Mexin}
partitions::list(9, MinPart = 2, MaxPart = 5)
\end{Mexin}
\begin{Mexout}
    [[5, 4], [5, 2, 2], [4, 3, 2], [3, 3, 3], [3, 2, 2, 2]]
\end{Mexout}
\begin{Mexin}
integerListsLexTools::list(9, 0, infinity, 2, 5, -infinity, 0)
\end{Mexin}
\begin{Mexout}
    [[5, 4], [5, 2, 2], [4, 3, 2], [3, 3, 3], [3, 2, 2, 2]]
\end{Mexout}
\eng{In fact, the algorithm of \Mup{combinat::integerListsLexTools} could also
  be used to generate Motzkin and Dyck words, etc.}

\eng{In the same spirit, instead of implementing a specific generator
  for standard tableaux, we implemented a generator for the linear
  extensions of a poset. We already reused this generator internally
  for generating standard binary search trees, and it could be reused
  as well for generating standard skew tableaux, standard ribbons, and
  so on\ifcolloquial (any volunteers?)\fi.}
\bigskip

\eng{We also incorporated and extended the former \Mex{CS} library by
  S.~Corteel, A.~Denise, I.~Dutour, and P.~Zimmermann. This library
  allows one to manipulate combinatorial classes that can be defined
  by a deterministic grammar. Here we consider words of A's and B's
  without two consecutive B's. Such a word is
  \begin{itemize}
  \item either void;
  \item either the word "B";
  \item either a word ending by a "A";
  \item or finally a word ending by "AB". 
  \end{itemize}
  In the two later case, the beginning of the word is of the same type. This
  can be used to build a recursion process for generating recursively all such
  words. Such a recursion process is called a grammar. Note that this process
  leads to an unambiguous grammar, that is each word is appears one and only
  one in the generation process, otherwise said the previous four cases are
  mutually exclusive. This is translated in \mupad{} by}
   \begin{Mexin}
fiWords := decomposableObjects(
    [FiWords = Union(Epsilon,
                     Atom(B),
                     Prod(FiWords, Atom(A)),
                     Prod(FiWords, Atom(A), Atom(B)))
    ]):
\end{Mexin}
\begin{Mexout}
\end{Mexout}
(Note: an \Mex{Epsilon} is an object of size 0 while an \Mex{Atom} is
an object of size 1).
\begin{Mexin}
fiWords::list(4)
\end{Mexin}
\begin{Mexout}
[Prod(Prod(Prod(B, A), A), A), Prod(

   Prod(Prod(Prod(Epsilon, A), A), A), A),

   Prod(Prod(Prod(Epsilon, A, B), A), A),

   Prod(Prod(B, A, B), A), Prod(Prod(Prod(Epsilon, A), A, B), A

   ), Prod(Prod(B, A), A, B), Prod(Prod(Prod(Epsilon, A), A),

   A, B), Prod(Prod(Epsilon, A, B), A, B)]
\end{Mexout}
\eng{The result is not very readable, but this can be fixed by a quick
  substitution:}
\begin{Mexin}
map(fiWords::list(4), p -> [eval(subs(p, Prod = id,
                                         Epsilon = null() ))])
\end{Mexin}
\begin{Mexout}
[[B, A, A, A], [A, A, A, A], [A, B, A, A], [B, A, B, A],

   [A, A, B, A], [B, A, A, B], [A, A, A, B], [A, B, A, B]]
\end{Mexout}
\eng{Alternatively, we could have provided some extra rewriting rules
  within the grammar. Notice that the preceding grammar generates the
  words in an order that is not so obvious. With some small reordering
  of the grammar, it is possible to ensure that the words are
  generated in the lexicographic order:}
\begin{Mexin}
fiWords := combinat::decomposableObjects(
    [FiWords    = Alias(FiWordsRec, DOM_LIST),
     FiWordsRec = Union(Epsilon(),
         Alias(Prod(Atom(A), FiWordsRec), op),
         Atom(B),
         Alias(Prod(Atom(B), Atom(A), FiWordsRec), op)
     )
    ]):
fiWords::list(4);
\end{Mexin}
\begin{Mexout}
[[A, A, A, A], [A, A, A, B], [A, A, B, A], [A, B, A, A],

   [A, B, A, B], [B, A, A, A], [B, A, A, B], [B, A, B, A]]
\end{Mexout}
\eng{This seems to work nicely. Let us count those words:}
\begin{Mexin}
fiWords::count(i) $ i = 0..10
\end{Mexin}
% $
\begin{Mexout}
            1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
\end{Mexout}
\eng{You will certainly recognize the Fibonacci sequence. Not quite a
  surprise, the recurrence relation can be seen right away from the
  grammar. Actually, this recurrence relation is automatically
  determined by the library, and used for counting efficiently:}
\begin{Mexin}
fiWords::recurrenceRelation() = 0
\end{Mexin}
\begin{Mexout}
                u(n - 1) - u(n) + u(n - 2) = 0
\end{Mexout}

\eng{
  \begin{sloppypar}
    This also applies for several libraries which are based on
    \Mup{combinat::decomposableObjects}. For example, here is the
    recurrence relation for binary trees:
  \end{sloppypar}
}
\begin{Mexin}
collect(binaryTrees::grammar::recurrenceRelation(),
        [u(n), u(n-1)], factor) = 0
\end{Mexin}
\begin{Mexout}
            u(n) (n + 1) - 2 u(n - 1) (2 n - 1) = 0
\end{Mexout}

\subsubsection{Defining new combinatorial classes}

\eng{For shortening the notations, we export the library \Mex{combinat}:}
\begin{Mexin}
  export(combinat):
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}

\eng{Let us define one of the most trivial combinatorial classes:}
\begin{Mexin}
domain oddIntegers
    // This is a graded combinatorial class:
    category Cat::GradedCombinatorialClass;
    // This is a domain (not a library):
    inherits Dom::BaseDomain;
    // This is a facade domain:
    axiom Ax::systemRep;

    info_str := "The class of non negative odd integers";

    isA := n -> bool(testtype(n, Type::PosInt) and
                     n mod 2 <> 0);
    // The size of an odd integer is itself
    size  := n -> n;
    count := n -> if n mod 2 = 1 then 1 else 0 end_if;
    list  := n -> if n mod 2 = 1 then [n] else [] end_if;

    // No need to define generator;
    // it is defined via list by default
end_domain:
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
\eng{In a first approximation, the three lines \Mex{inherits},
  \Mex{category}, and \Mex{axiom} may be safely ignored and kept
  verbatim. For a deeper understanding, we strongly recommend to read
  the detailed explanations about the implementation of combinatorial
  classes in the \Mhref[index,designCombinatorialClasses]{design
    notes}.}

\eng{Now, this combinatorial class can be used like all the others:}
\begin{Mexin}
testtype(x, oddIntegers), testtype(-3, oddIntegers),
testtype(2, oddIntegers), testtype(3, oddIntegers);
\end{Mexin}
\begin{Mexout}
                   FALSE, FALSE, FALSE, TRUE
\end{Mexout}
\begin{Mexin}
oddIntegers::count(3);
\end{Mexin}
\begin{Mexout}
                               1
\end{Mexout}
\begin{Mexin}
oddIntegers::list(5)
\end{Mexin}
\begin{Mexout}
                              [5]
\end{Mexout}

\eng{In particular, it can be used as building block for constructing
  new combinatorial classes like, say, integer partitions with odd
  parts:}
  \begin{Mexin}
oddPartsPartitions := combinat::decomposableObjects
                         ([P = Multiset(oddIntegers)]):
  \end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
  \begin{Mexin}
oddPartsPartitions::list(5)
  \end{Mexin}
  \begin{Mexout}
   [Multiset(5), Multiset(1, 1, 3), Multiset(1, 1, 1, 1, 1)]
  \end{Mexout}

\ifincludeExercises
\eng{
  \begin{sloppypar}
    Exercise: Improve the definition above so that
    \Mex{oddIntegers::count(-1)} raises an error instead of
    returning $-1$.
  \end{sloppypar}
}
\fi

\eng{It is often practical to define a sub-class of an existing class.
  Here we show how to define the class of the permutations of
  \Mex{[1,2,3]}:}
\begin{Mexin}
domain permutationsOf123
    category Cat::CombinatorialClass;
    // Inherits all the methods from combinat::permutations
    inherits permutations;
    axiom    Ax::systemRep;

    info_str := "the class of the permutations of [1,2,3]";

    // Redefinition of isA, count and generator
    isA := (p) -> permutations::isA(p, [1,2,3]);
    count     := () -> permutations::count([1,2,3]);
    generator := () -> permutations::generator([1,2,3]);

    // No need to redefine list, since it is
    // defined via generator by default
end_domain:
\end{Mexin}
%\begin{Mexout}
%\end{Mexout}
\eng{Let us use this new combinatorial class:}
\begin{Mexin}
testtype(x,            permutationsOf123),
testtype([1, 2, 3, 4], permutationsOf123),
testtype([1, 2, 2],    permutationsOf123),
testtype([1, 3, 2],    permutationsOf123);
\end{Mexin}
\begin{Mexout}
                   FALSE, FALSE, FALSE, TRUE
\end{Mexout}
\begin{Mexin}
permutationsOf123::count();
\end{Mexin}
\begin{Mexout}
                               6
\end{Mexout}
\begin{Mexin}
permutationsOf123::list()
\end{Mexin}
\begin{Mexout}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2],

   [3, 2, 1]]
\end{Mexout}
\eng{Note: instead of implementing \Mex{permutationsOf123} by hand,
  we could have alternatively used the generic utility
  \Mup{combinat::subClass}; it allows one to automatically define a
  sub-class of an existing combinatorial class by providing extra
  parameters to be passed down to all the methods \Mex{count},
  \Mex{list}, etc.:}
\begin{Mexin}
permutationsOf123 := subClass(permutations, Parameters = 3):
permutationsOf123::list()
\end{Mexin}
\begin{Mexout}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2],

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

\ifincludeExercises
\eng{Exercises:
  \begin{itemize}
  \item Define a parametrized domain \Mex{permutationsOf(m)} for the
    permutations of the list \Mex{m} (or of \Mex{[1..m]} if \Mex{m} is
    an integer);
  \item Define the combinatorial class of prime integers;
  \item Define a parametrized domain \Mex{classOfSet(\{a,b,c\})} that
    creates the trivial combinatorial class composed of the elements
    \Mex{a}, \Mex{b}, and \Mex{c}. You may assume that all the
    elements of the set are identifiers, and define the \Mex{domtype}
    entry as \Mex{DOM_IDENT}.
  \end{itemize}
}
\fi

\eng{To conclude, we define the combinatorial class of Fibonacci
  words. Essentially, we reuse the definition of \Mex{fiWords} above,
  and wrap it into a domain to add type checking:}
\begin{Mexin}
domain FibonacciWords
    // The objects of this class are defined by a grammar
    category Cat::DecomposableClass;
    inherits Dom::BaseDomain;
    axiom    Ax::systemRep;

    info_str := "the class of Fibonacci words";

    // The domain of the elements of this class
    domtype := DOM_LIST;

    // The type of the elements of this class:
    // a procedure that tests if w is a Fibonacci word
    isA := proc(w : Type::AnyType,
                size = 0 : Type::NonNegInt)
        local i;
        begin
            if domtype(w)<>DOM_LIST then return(FALSE); end_if;
            for i from 1 to nops(w) do
                if (w[i]<>A and w[i]<>B) or
                   (i<nops(w) and w[i]=B and w[i+1]=B) then
                    return(FALSE);
                end_if;
            end_for;
            if args(0) = 1 then TRUE else
                bool(nops(w) = size);
            end_if;
        end_proc;

    // The size of a Fibonacci word is its length
    size := nops;

    // The grammar which defines the objects of this class
    grammar := decomposableObjects(
        [FiWords    = Alias(FiWordsRec, DOM_LIST),
         FiWordsRec = Union(
             Epsilon(),
             Alias(Prod(Atom(A), FiWordsRec), op),
             Atom(B),
             Alias(Prod(Atom(B), Atom(A), FiWordsRec), op))]);
end_domain:
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
Now, we can do type checking with this domain:
\begin{Mexin}
testtype(x, FibonacciWords),
testtype([A, B, C], FibonacciWords),
testtype([A, B, B], FibonacciWords),
testtype([A, B, A], FibonacciWords)
\end{Mexin}
\begin{Mexout}
                   FALSE, FALSE, FALSE, TRUE
\end{Mexout}
And of course, we can still use all the previous functionalities of \Mex{fiWords}:
\begin{Mexin}
FibonacciWords::list(4);
\end{Mexin}
\begin{Mexout}
[[A, A, A, A], [A, A, A, B], [A, A, B, A], [A, B, A, A],

   [A, B, A, B], [B, A, A, A], [B, A, A, B], [B, A, B, A]]
\end{Mexout}
\begin{Mexin}
FibonacciWords::count(4);
\end{Mexin}
\begin{Mexout}
                               8
\end{Mexout}
\eng{And finally if we wanted to extract the second element of the list
  without expanding it we can ask for the words of rank \Mex{2} in the list:}
\begin{Mexin}
FibonacciWords::unrank(2, 4)
\end{Mexin}
\begin{Mexout}
                         [A, A, A, B]
\end{Mexout}

\ifincludeExercises
\eng{Exercises:
  \begin{itemize}
  \item Add two methods \Mex{toString} and \Mex{fromString} which
    converts a Fibonacci word to and from a string.
  \item Define a parametrized domain \Mex{FibonacciWords(A,B)} for the
    Fibonacci words on the letter \Mex{A} and \Mex{B}.
  \end{itemize}
}
\fi

\subsubsection{Using predefined combinatorial algebras}

\eng{We now demonstrate how to do sample computations with predefined
  combinatorial algebras, starting with the algebra of symmetric
  functions. Note that we really consider those predefined algebras as
  mere examples of use of this package; important and useful examples
  of course, but just examples.}

\eng{We define the ring of symmetric functions over the rational
  numbers:}
\begin{Mexin}
S := examples::SymmetricFunctions(Dom::Rational);
\end{Mexin}
\begin{Mexout}
          examples::SymmetricFunctions(Dom::Rational)
\end{Mexout}
\eng{This ring has several remarkable families like the symmetric
  \emph{power-sums} $p_k$: recall that the symmetric power-sum $p_k$
  expands on any given specified \emph{alphabet} (i.e. set of
  variables) as the sum of all the variables elevated to the power
  $k$; furthermore, given a partition
  $\lambda:=(\lambda_1,\dots,\lambda_k)$, the product of
  $p_{\lambda_1}\dots p_{\lambda_k}$ is denoted by $p_\lambda$:}
\begin{Mexin}
p1 := S::p([1]);
p1([x, y, z]);
\end{Mexin}
\begin{Mexout}
                             p[1]

                           x + y + z
\end{Mexout}
\begin{Mexin}
p2 := S::p([2]);
p2([x, y, z])
\end{Mexin}
\begin{Mexout}
                             p[2]

                          2    2    2
                         x  + y  + z
\end{Mexout}
\begin{Mexin}
p421 := S::p([4, 2, 1]);
p421([x,y,z])
\end{Mexin}
\begin{Mexout}
                          p[4, 2, 1]

             2    2    2    4    4    4
           (x  + y  + z ) (x  + y  + z ) (x + y + z)
\end{Mexout}
Note: the product being commutative, the order in which the terms
appear in the expansion above depends on \mupad{} internal order, and
is mathematically irrelevant.

Actually, the ring of symmetric functions is the free commutative
algebra on the symmetric power-sums:
\begin{Mexin}
p2 * p1 * p2 * p421
\end{Mexin}
\begin{Mexout}
                      p[4, 2, 2, 2, 1, 1]
\end{Mexout}
\eng{Note that any expression is immediately expanded by the system:}
\begin{Mexin}
(p421 + 3*p2)*(1/4*p1 - p2)
\end{Mexin}
\begin{Mexout}
  1/4 p[4, 2, 1, 1] - 3 p[2, 2] - p[4, 2, 2, 1] + 3/4 p[2, 1]
\end{Mexout}
\eng{This happens because the call \Mex{S::p([1])} returns a typed
  object, for which the standard arithmetic operators are overloaded:}
\begin{Mexin}
domtype(p1);
\end{Mexin}
\begin{Mexout}
  examples::SymmetricFunctionsTools::powersum(Dom::Rational)
\end{Mexout}
\begin{Mexin}
S::p
\end{Mexin}
\begin{Mexout}
  examples::SymmetricFunctionsTools::powersum(Dom::Rational)
\end{Mexout}
\eng{That is, \Mex{S::powersum} (or \Mex{S::p} for short) really
  represents the domain of symmetric functions expanded on the
  power-sums basis. If at some time you do not want the expansion to
  take place, the objects can always be converted to expressions:}
  \begin{Mexin}
f := (expr(p421) + 3*expr(p2))*(1/4*expr(p1) - expr(p2))
  \end{Mexin}
  \begin{Mexout}
                                   / p[1]        \
             (3 p[2] + p[4, 2, 1]) | ---- - p[2] |
                                   \   4         /
  \end{Mexout}
\eng{This expression can by converting back to a symmetric function :}
  \begin{Mexin}
S(f);
  \end{Mexin}
  \begin{Mexout}
  1/4 p[4, 2, 1, 1] - 3 p[2, 2] - p[4, 2, 2, 1] + 3/4 p[2, 1]
  \end{Mexout}
  \eng{To do this we use the following small trick because of the indexed
    notation for the basis elements.}
  \begin{Mexin}
eval(subs(f, p = S::p::domainWrapper))
  \end{Mexin}
  \begin{Mexout}
  1/4 p[4, 2, 1, 1] - 3 p[2, 2] - p[4, 2, 2, 1] + 3/4 p[2, 1]
  \end{Mexout}
  \eng{The explanation of the trick is that \Mex{S::p::domainWrapper} is a
    special \mupad\ object which, when used as \Mex{S::p::domainWrapper[3,2]},
    returns a call to \Mex{S::p([3,2])}.}

\eng{Of course, \Mup{examples::SymmetricFunctions} provides the other
  classical bases of symmetric functions, like the elementary
  symmetric functions \Mex{S::e}, the monomial symmetric functions
  \Mex{S::m}, the homogeneous symmetric functions \Mex{S::h}, the
  Schur functions \Mex{S::s}, etc.: }
\begin{Mexin}
expand(S::e([2])([x,y,z]))
\end{Mexin}
\begin{Mexout}
                        x y + x z + y z
\end{Mexout}
\begin{Mexin}
expand(S::m([2, 1])([x,y,z]))
\end{Mexin}
\begin{Mexout}
               2    2        2    2        2    2
            x y  + x  y + x z  + x  z + y z  + y  z
\end{Mexout}
\begin{Mexin}
expand(S::h([2])([x,y,z]))
\end{Mexin}
\begin{Mexout}
                                   2    2    2
                x y + x z + y z + x  + y  + z
\end{Mexout}
\begin{Mexin}
expand(S::s([2])([x,y,z]))
\end{Mexin}
\begin{Mexout}
                                   2    2    2
                x y + x z + y z + x  + y  + z
\end{Mexout}

\eng{Here is how to convert from one basis to the other}:
\begin{Mexin}
f := S::p([4]);
S::e(f);
S::h(f);
S::s(f);
S::m(f)
\end{Mexin}
\begin{Mexout}
                             p[4]

 e[1, 1, 1, 1] - 4 e[2, 1, 1] + 4 e[3, 1] - 4 e[4] + 2 e[2, 2]

- h[1, 1, 1, 1] + 4 h[2, 1, 1] - 4 h[3, 1] + 4 h[4] - 2 h[2, 2]

         - s[1, 1, 1, 1] + s[2, 1, 1] - s[3, 1] + s[4]

                             m[4]
\end{Mexout}
\eng{When multiplying two symmetric functions which are not expressed
  in the same basis, the system will make an implicit conversion, and
  return the result in one or the other of the two bases:}
\begin{Mexin}
S::m([2]) * S::s([2])
\end{Mexin}
\begin{Mexout}
            m[2, 1, 1] + m[3, 1] + m[4] + 2 m[2, 2]
\end{Mexout}
\eng{If you want to force the product to be done on a given basis, you
  can call the proper conversion explicitly:}
\begin{Mexin}
S::s(S::m([2])) * S::s([2]);
\end{Mexin}
\begin{Mexout}
                 - s[2, 1, 1] + s[4] + s[2, 2]
\end{Mexout}
\eng{Now, we can combine everything, and do some complicated
  calculation:}
% Alessandra: très joli!
\begin{Mexin}
S::p( S::m([1]) * ( S::e([3])*S::s([2]) + S::s([3]) ) )
\end{Mexin}
\begin{Mexout}
1/12 p[1, 1, 1, 1, 1, 1] + 1/6 p[3, 2, 1] -

   1/6 p[2, 1, 1, 1, 1] + 1/6 p[3, 1, 1, 1] -

   1/4 p[2, 2, 1, 1] + 1/6 p[1, 1, 1, 1] + 1/2 p[2, 1, 1] +

   1/3 p[3, 1]
\end{Mexout}
%  \eng{As a last example, we show how to convert an expression mixing
%    elements of several basis into one of the basis:}

\eng{Finally, there is some basic support for the Hall-Littlewood
  functions, in the $P$ and $Q'$ basis, which we demonstrate now.  We
  need to take some ground field which contains the parameter $t$ of
  those functions. The simplest (and actually most efficient with the
  current \mupad{} version), is to take the full field of expressions
  as coefficient ring:}
\begin{Mexin}
S := examples::SymmetricFunctions(Dom::ExpressionField()):
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
\eng{Here is the Hall-Littlewood function $Q'_{(3,2,1,1)}$:}
\begin{Mexin}
el := S::QP([3, 2, 1, 1])
\end{Mexin}
\begin{Mexout}
                        QP[3, 2, 1, 1]
\end{Mexout}
\eng{The expansion of \Mex{el} in terms of Schur functions reads as:}
\begin{Mexin}
S::s(el)
\end{Mexin}
\begin{Mexout}
                     2
t s[3, 2, 2] + (t + t ) s[3, 3, 1] + t s[4, 1, 1, 1] +

     2    3    4              2    3    4
   (t  + t  + t ) s[4, 3] + (t  + t  + t ) s[5, 1, 1] +

       3    4    5              4    5    6
   (2 t  + t  + t ) s[5, 2] + (t  + t  + t ) s[6, 1] +

    7                                2    3
   t  s[7] + s[3, 2, 1, 1] + (t + 2 t  + t ) s[4, 2, 1]
\end{Mexout}
\eng{The expansion of \Mex{el} on the alphabet $(q,qt)$ reads as:}
\begin{Mexin}
expand(el([q, q*t]))
\end{Mexin}
\begin{Mexout}
   7  5      7  6       7  7      7  8      7  9      7  10
4 q  t  + 7 q  t  + 10 q  t  + 9 q  t  + 6 q  t  + 5 q  t   +

      7  11      7  12    7  13    7  14
   3 q  t   + 2 q  t   + q  t   + q  t
\end{Mexout}

% Alessandra: insert a break or make a new section

\subsubsection{Defining new combinatorial algebras}

\eng{We now turn to the central feature of the \mupadcombinat{}
  package: the ability to easily implement new combinatorial algebras.
  We start by the free associative algebra over the rational numbers
  generated by non commutative letters $a,b,c,d,\dots$. Its basis is
  indexed by words, and the product of two basis elements is obtained
  by concatenating the corresponding words:}
% TODO: add info line to all combinatorial algebras below
% Alessandra: explain the dom::term @ _concat; same thing for
% FreeCommutativeAlgebra 

\begin{Mexin}
domain FreeAlgebra
    inherits Dom::FreeModule(Dom::Rational, combinat::words);
    category Cat::AlgebraWithBasis(Dom::Rational);

    one           := dom::term([]);
    mult2Basis    := dom::term @ _concat;
end_domain:
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
We will explain the bits of this definition in a minute after a few
examples of use. Let us define two elements of the free algebra:
\begin{Mexin}
x := FreeAlgebra([a, b, c]);
y := FreeAlgebra([d, e])
\end{Mexin}
\begin{Mexout}
                         B([a, b, c])

                           B([d, e])
\end{Mexout}
The \Mex{B} just stands for the name of the basis. We can compute
linear combinations and products of \Mex{x} and \Mex{y}:
\begin{Mexin}
3 * x;
x + y;
x * y
\end{Mexin}
\begin{Mexout}
                        3 B([a, b, c])

                   B([d, e]) + B([a, b, c])

                      B([a, b, c, d, e])
\end{Mexout}
% Alessandra: why are the terms inverted in the sum ?
Here is a more complicated expression:
  \begin{Mexin}
x * (2*x + y) + (3 + y/2)^2
  \end{Mexin}
  \begin{Mexout}
1/4 B([d, e, d, e]) + 2 B([a, b, c, a, b, c]) +

   B([a, b, c, d, e]) + 3 B([d, e]) + 9 B([])
\end{Mexout}
\eng{Note how the \Mex{3} in the expression is automatically converted
  into an element of the domain; declaring that \Mex{FreeAlgebra} was
  an algebra (with a unit) automatically defined the natural embedding
  of the coefficient ring into it.}

% Alessandra: put those explanations directly in comments in the
% code above, as done for defining combinatorial classes

We turn to the explanation of the implementation of \Mex{FreeAlgebra}
above. The line
\begin{Mvin}{prompt=,click=false,test=false}
  domain FreeAlgebra
\end{Mvin}
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
states that we are defining a new \emph{domain} called
\Mex{FreeAlgebra} (a new class in the usual object oriented
terminology). 
\begin{Mvin}{prompt=,click=false,test=false}
   inherits Dom::FreeModule(Dom::Rational, combinat::words);
\end{Mvin}
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
lets \Mex{FreeAlgebra} inherit its
implementation from the free module over the rationals
(\Mup{Dom::Rational}) with basis indexed by words
(\Mup{combinat::words}).
\begin{Mvin}{prompt=,click=false,test=false}
   category Cat::AlgebraWithBasis(Dom::Rational);
\end{Mvin}
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
states that \Mex{FreeAlgebra} is
actually an algebra with a distinguished basis; this allows one, in
particular, to define the multiplication by linearity on the basis.
\begin{Mvin}{prompt=,click=false,test=false}
   one           := dom::term([]);
\end{Mvin}
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
defines that the unit of \Mex{FreeAlgebra} is the empty word
(\Mex{dom} refers to the domain being defined, and \Mex{dom::term} is
a constructor that takes an element of the basis, and returns it as an
element of the domain).  Finally,
\begin{Mvin}{prompt=,click=false,test=false}
   mult2Basis    := dom::term @ _concat;
\end{Mvin}
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
states that two elements of
the basis are multiplied by concatenating them, and making an element
of the domain with the result (\Mex{@}~denotes the composition of
functions). That's it.
\medskip

Let us define the free commutative algebra on the letters
$a,b,c,\dots$:
\begin{Mexin}
domain FreeCommutativeAlgebra
    inherits  Dom::FreeModule(Dom::Rational, combinat::words);
    category Cat::AlgebraWithBasis(Dom::Rational);

    one		    := dom::term([]);
    straightenBasis := dom::term @ sort;
    mult2Basis      := dom::straightenBasis @ _concat;
end_domain:
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
\begin{sloppypar}
  \noindent
%  As one can see, we simply inherit from \Mex{FreeAlgebra} and just
%  redefine the product: using domains (and in general object-oriented
%  programming) helps reusing code.
  Note that we cheated a little bit: we declared that the basis of
  \Mex{FreeCommutativeAlgebra} consisted of words, whereas it really
  consists of words up to permutation of its letters: \Mex{B([a,b])}
  and \Mex{B([b,a])} represent the same element of the algebra. A
  careful implementation should define the combinatorial class of
  words up to permutation, and use it as the basis of
  \Mex{FreeCommutativeAlgebra}.
\end{sloppypar}

To enforce the uniqueness of the representation, we straighten the
words in the basis by sorting them. This is the job of the
\Mex{straightenBasis} constructor.
\begin{Mexin}
x := FreeCommutativeAlgebra([a, b]);
y := FreeCommutativeAlgebra([c, b, a])
\end{Mexin}
\begin{Mexout}
                           B([a, b])

                         B([a, b, c])
\end{Mexout}
The product of two words is then defined by concatenating them and
straightening the result:
\begin{Mexin}
x * y;
y * x
\end{Mexin}
\begin{Mexout}
                      B([a, a, b, b, c])

                      B([a, a, b, b, c])
\end{Mexout}
If efficiency was at a premium, instead of sorting the concatenation of the
two lists, we could have used the \mupad{} function \Mup{listlib::merge} which
merges sorted lists.

Note that two elements of \Mex{FreeCommutativeAlgebra} and of
\Mex{FreeAlgebra} may happen to be printed out the same way:
\begin{Mexin}
x := FreeAlgebra([a]);
y := FreeCommutativeAlgebra([a])
\end{Mexin}
\begin{Mexout}
                            B([a])

                            B([a])
\end{Mexout}
and even share the exact same internal representation:
\begin{Mexin}
bool(extop(x) = extop(y))
\end{Mexin}
\begin{Mexout}
                             TRUE
\end{Mexout}
However, they are not equal, because they are not in the same domain:
\begin{Mexin}
bool(x = y);
domtype(x), domtype(y)
\end{Mexin}
\begin{Mexout}
                             FALSE

              FreeAlgebra, FreeCommutativeAlgebra
\end{Mexout}
So, even if they share the same name of basis, there is no risk of
confusion; for example we are not allowed to multiply them together:
\begin{Mexin}
x * y
\end{Mexin}
\begin{Mexout}
Error: Don't know how to multiply a FreeAlgebra by a FreeCommu\
tativeAlgebra
\end{Mexout}
Of course, this is still confusing for the user. He or she may always
customize the basis names (as many other things) at any time should he
or she wish to do so:
\begin{Mexin}
FreeAlgebra::basisName            := hold(T):
FreeCommutativeAlgebra::basisName := hold(S):
x, y
\end{Mexin}
% Alessandra: ? near the x,y
\begin{Mexout}
                        T([a]), S([a])
\end{Mexout}
Here, \Mex{T} stands for ``Tensor algebra'', while \Mex{S} stands for
``Symmetric algebra''. The \Mup{hold} is there for safety, in case one
of the identifiers \Mex{T} or \Mex{S} is assigned a value.

\begin{sloppypar}
  We can define the natural evaluation morphism from \Mex{FreeAlgebra}
  to \Mex{FreeCommutativeAlgebra} by linearity on the words; a word
  itself is simply sorted, and converted into an element of
  \Mex{FreeCommutativeAlgebra}:
\end{sloppypar}
% Should we demonstrate there how evaluation can be overloaded ?
\begin{Mexin}
evaluation := operators::makeLinear
                  (FreeCommutativeAlgebra::term @ sort,
                   Source   = FreeAlgebra,
                   ImageSet = FreeCommutativeAlgebra):
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
Let us apply this morphism to the sum of two words which only differ by
a permutation:
\begin{Mexin}
x := FreeAlgebra([c, b, a]) + FreeAlgebra([c, a, b]);
\end{Mexin}
\begin{Mexout}
                  T([c, a, b]) + T([c, b, a])
\end{Mexout}
\begin{Mexin}
evaluation(x);
\end{Mexin}
\begin{Mexout}
                        2 S([a, b, c])
\end{Mexout}
\begin{sloppypar}
  The evaluation morphism is actually quite canonical, so it can make
  sense to declare it as a conversion to the system. This can be
  achieved with the \Mup{operators::overloaded::declareConversion}
  function:
\end{sloppypar}
\begin{Mexin}
operators::overloaded::declareConversion(
    FreeAlgebra, FreeCommutativeAlgebra, evaluation):
FreeCommutativeAlgebra(x)
\end{Mexin}
\begin{Mexout}
                        2 S([a, b, c])
\end{Mexout}
Here, the conversion has been declared as implicit. If an expression
mixes elements of \Mex{FreeAlgebra} and \Mex{FreeCommutativeAlgebra},
the former are automatically converted into
\Mex{FreeCommutativeAlgebra}:
\begin{Mexin}
FreeCommutativeAlgebra([a, b]) + FreeAlgebra([c,b,a])
\end{Mexin}
\begin{Mexout}
                   S([a, b]) + S([a, b, c])
\end{Mexout}
Of course, such a feature is questionable. Depending on the context,
it can prove very practical, or on the contrary dangerous. The user is
the only judge, and she or he can restrict the scope of this
conversion by using the \Mex{Explicit} option. In this case, the
conversion will only be applied if requested explicitly by
\Mup{convert} or by \Mex{new}:
\begin{Mexin}
operators::overloaded::declareConversion(
      FreeAlgebra, FreeCommutativeAlgebra,
      evaluation, Explicit):
FreeCommutativeAlgebra(x);
\end{Mexin}
\begin{Mexout}
                        2 S([a, b, c])
\end{Mexout}
\begin{Mexin}
FreeCommutativeAlgebra([a, b]) + FreeAlgebra([c,b,a])
\end{Mexin}
\begin{Mexout}
Error: Don't know how to add a FreeCommutativeAlgebra and a Fr\
eeAlgebra
\end{Mexout}
Typically, for symmetric functions, we only provided explicit
conversions to construct symmetric functions from partitions because
those conversions are not canonical at all: the Schur function
\Mex{s[3,2,1]} obtained by converting the partition \Mex{[3,2,1]} has
nothing to do with the elementary function \Mex{e[3,2,1]}. We refer to
the \Mhref[index,designOverloading]{design notes} and to the
documentation of the \Mup{operators::overloaded} library for details
on the mechanism we use for defining automatic conversions and
overloaded operators and functions. Note that it is not (yet)
completely possible to declare new conversions as above when the
target domain of the conversion is one of the predefined domains of
the \mupad{} library.

% Alessandra: insert a break
\subsubsection{Combinatorial algebras with several representations}

\eng{As usual, for shortening the notations, we export the library
  \Mex{combinat}:}
\begin{Mexin}
  export(combinat):
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}

To continue our exploration, we implement variations on the two
previous domains, where we assume that the algebra generators are
indexed by \Mex{1,2,\Mseq{}}. The basis elements of the free algebra
and of the free commutative algebra are now respectively indexed by
compositions and partitions.
\begin{Mexin}
domain FreeAlgebraInteger
    inherits Dom::FreeModule(Dom::Rational,
                             compositions);
    category Cat::AlgebraWithBasis(Dom::Rational);

    basisName       := hold(E);
    exprTerm        := dom::exprTermIndex;
    one             := dom::term([]);
    mult2Basis      := dom::term @ _concat;
end_domain:
domain FreeCommutativeAlgebraInteger
    inherits Dom::FreeModule(Dom::Rational,
                             partitions);
    category Cat::AlgebraWithBasis(Dom::Rational);

    basisName       := hold(e);
    exprTerm        := dom::exprTermIndex;
    one             := dom::term([]);
    straightenBasis := dom::term @ revert @ sort;
    mult2Basis      := dom::straightenBasis @ _concat;
end_domain:
\end{Mexin}
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
The reader may have recognized here respectively the commutative and
non commutative symmetric functions, expanded on some multiplicative
basis. To shorten the notations, we define two aliases, and declare
the same evaluation conversion as before:
\begin{Mexin}
alias(NCSF = FreeAlgebraInteger,
      SF   = FreeCommutativeAlgebraInteger):
operators::overloaded::declareConversion(NCSF, SF,
    operators::makeLinear(SF::straightenBasis,
                          Source   = NCSF,
                          ImageSet = SF)):
\end{Mexin}
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
\begin{Mexin}
x := NCSF([1, 3, 2]);
\end{Mexin}
\begin{Mexout}
                          E[1, 3, 2]
\end{Mexout}
\begin{Mexin}
y := SF  ([1, 3, 2])
\end{Mexin}
\begin{Mexout}
                          e[3, 2, 1]
\end{Mexout}
\begin{Mexin}
SF(x)
\end{Mexin}
\begin{Mexout}
                          e[3, 2, 1]
\end{Mexout}
\begin{Mexin}
bool(SF(x)=y)
\end{Mexin}
\begin{Mexout}
                             TRUE
\end{Mexout}
\eng{
  \begin{sloppypar}
    Let us analyze the differences with our previous implementation of
    the free algebras. First, we chose an indexed notation for the
    basis elements, as this notation is more compact and quite
    conventional in other systems. This is the purpose of the line
    \Mex{exprTerm := dom::exprTermIndex}: the method \Mex{exprTerm}
    of the domain is called to convert a term into an
    expression, as well as to print a term if there is no
    \Mex{printTerm} method; \Mex{dom::exprTermIndex} is a possible
    implementation of \Mex{exprTerm}, inherited from the category,
    which gives indexed notations. The other difference is that,
    following the usual convention, the integers in the partitions are
    sorted decreasingly. Here, this is suboptimally achieved by
    reverting the list after sorting it in the
    \Mex{SF::straightenBasis} method.
  \end{sloppypar}
}

A disadvantage of this implementation of \Mex{SF} is that elements
with many repetitions are not represented compactly:
\begin{Mexin}
SF([1])^10
\end{Mexin}
\begin{Mexout}
                e[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
\end{Mexout}
One might prefer to use another basis for \Mex{SF}, where the element above
would be represented as the first generator to the power $10$. This can
be done \emph{via} the usual exponent notation for partitions. The
basis of the algebra now consists of integer vectors. The product of
two elements is simply obtained by adding up the vectors part by part,
which can conveniently be implemented using the \Mup{zip} \mupad{}
function.
\begin{Mexin}
domain SFExp
    inherits Dom::FreeModule(Dom::Rational,
                             combinat::integerVectors);
    category Cat::AlgebraWithBasis(Dom::Rational);

    basisName       := hold(e);
    exprTerm        := dom::exprTermIndex;
    one             := dom::term([]);
    mult2Basis      :=
         (v1,v2) -> dom::term(zip(v1,v2,_plus,0));
end_domain:
\end{Mexin}
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
Let us do some computations:
\begin{Mexin}
SFExp([1]);
SFExp([2, 0, 1])*SFExp([1, 1]);
SFExp([1])^10
\end{Mexin}
\begin{Mexout}
                             e[1]

                          e[3, 1, 1]

                             e[10]
\end{Mexout}
This notation could be confusing, so we override it:
\begin{Mexin}
SFExp::exprTerm :=
    v -> _mult(dom::basisName.i^v[i] $ i=1..nops(v)):
SFExp([1]);
SFExp([2, 0, 1])*SFExp([1, 1]);
SFExp([1])^10
\end{Mexin}
% $
\begin{Mexout}
                              e1

                             3
                           e1  e2 e3

                               10
                             e1
\end{Mexout}
As is, the elements of this algebra are not uniquely represented. For
example, the first generator of the algebra can be represented by any
of \Mex{[1], [1,0], [1,0,0], \Mseq{}}:
\begin{Mexin}
SFExp([1]), SFExp([1, 0]), SFExp([1, 0, 0]);
bool(SFExp([1]) = SFExp([1, 0]))
\end{Mexin}
\begin{Mexout}
                          e1, e1, e1

                             FALSE
\end{Mexout}
\eng{We leave it up as an exercise for the reader to fix this bug by
  implementing a \Mex{straightenBasis} method which strips out the
  trailing zeroes of the basis elements.}
\eng{
  \begin{sloppypar}
    Of course, \Mex{SF} and \Mex{SFExp} really represent the same
    algebra; only the internal data representation changes. So, we
    provide as conversions the reciprocal isomorphisms obtained by
    extending by linearity the bijections
    \Mup{combinat::partitions::fromExp} and
    \Mup{combinat::partitions::toExp}:
  \end{sloppypar}}
\begin{Mexin}
operators::overloaded::declareConversion(SFExp, SF,
    operators::makeLinear(
        SF::term @ combinat::partitions::fromExp,
        Source = SFExp, ImageSet = SF)):
operators::overloaded::declareConversion(SF, SFExp,
    operators::makeLinear(
        SFExp::term @ combinat::partitions::toExp,
        Source = SF, ImageSet = SFExp)):
\end{Mexin}
Here is a simple conversion:
\begin{Mexin}
SF([4, 3, 3, 1]), SFExp(SF([4, 3, 3, 1]))
\end{Mexin}
\begin{Mexout}
                                       2
                   e[4, 3, 3, 1], e1 e3  e4
\end{Mexout}
Let us check on an example that the conversions are indeed morphisms:
\begin{Mexin}
x := SF([3, 1]):
y := SF([4, 3, 2]):
x * y, SF( SFExp(x) * SFExp(y) )
\end{Mexin}
\begin{Mexout}
              e[4, 3, 3, 2, 1], e[4, 3, 3, 2, 1]
\end{Mexout}
We can write expressions that mix elements of both domains, and let
the system find a way to convert them appropriately:
\begin{Mvin}{test=false}
( 1 + SF([3, 1])*x ) * SFExp([2, 0]) + SFExp([1])
\end{Mvin}
\begin{Mvout}{test=false}
                        4   2     2
                      e1  e3  + e1  + e1
\end{Mvout}
A priori, the representation of the result cannot be predicted; it
depends on how the overloading mechanism chooses to resolve the
conversions. If the user prefers one of the representations, she or he
can take over the control at any level of the expression by forcing
proper conversions:
\begin{Mexin}
    (1+SF([3,1])*x) * SF( SFExp([2,0]) )  +  SF( SFExp([1]) ) ;
SF( (1+SF([3,1])*x) *     SFExp([2,0]) )  +  SF( SFExp([1]) ) ;
SF( (1+SF([3,1])*x) *     SFExp([2,0])    +      SFExp([1]) ) ;
\end{Mexin}
\begin{Mexout}
             e[3, 3, 1, 1, 1, 1] + e[1, 1] + e[1]

             e[3, 3, 1, 1, 1, 1] + e[1, 1] + e[1]

             e[3, 3, 1, 1, 1, 1] + e[1, 1] + e[1]
\end{Mexout}

The implicit conversions are automatically applied transitively. As a
consequence, we have without further work a conversion from \Mex{NCSF}
to \Mex{SF}:
\begin{Mexin}
SFExp(NCSF([1, 4, 2, 2]))
\end{Mexin}
\begin{Mexout}
                                2
                           e1 e2  e4
\end{Mexout}
Another consequence is that, when there are $n$ different
representations for an algebra (say the symmetric functions expressed
on any of the \Mex{p}, \Mex{e}, \Mex{m}, \Mex{h}, or \Mex{s} basis),
it is sufficient \emph{a priori} to implement $n$ conversions to be able to
get all the $n(n-1)$ possible conversions. In practice, we usually
implement $2(n-1)$ conversions, so that no conversion takes more than
two steps. Of course it is still possible to implement some extra
direct conversions for improved efficiency; when there are several
ways to convert an element from one domain to another, the system
always uses one of the shortest ones.


\subsubsection{A practical research example: the $q$-shuffle algebra}

\eng{As usual, for shortening the notations, we export the library
  \Mex{combinat}:}
\begin{Mexin}
  export(combinat):
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}

\newcommand{\shuffle}{{\,\sqcup\!\sqcup\,}}
As a more advanced example, we demonstrate some computations in the so-called
$q$-shuffle algebra. This algebra has the sets of words for basis. The product
is defined recursively by
  $$\epsilon \shuffle w = w \shuffle \epsilon  = w$$
  $$ua \shuffle vb := (ua \shuffle v) b + q^{|vb|} (u \shuffle vb) a.$$
where $\epsilon$ is the empty word, $u,v,w$ are words, $a,b$ letters and $|w|$
denotes the length of the word $w$.
  \begin{Mexin}
domain qShuffleAlgebra(K: DOM_DOMAIN)
    // The parameter K is the base field
    
    // Implementation of the vector space structure
    inherits Dom::FreeModule(K, words);

    // This is an algebra with a distinguished basis
    category Cat::AlgebraWithBasis(K);

    // Basis elements are printed as W([a,b,a,a])
    basisName     := hold(W);

    // The unit of the algebra is the empty word
    one           := dom::term([]);

    // The binary product of the algebra is defined
    // by linearity on basis elements
    mult2Basis    :=
    proc(ua: dom::basisIndices, vb: dom::basisIndices)
        local a, b, u, v;
    begin
    // Base case: ua is empty
        if nops(ua)=0 then return(dom::term(vb)); end_if;
    // Base case: vb is empty
        if nops(vb)=0 then return(dom::term(ua)); end_if;
    // extract u and a from ua
        u := [op(ua, 1..nops(ua)-1)]; a := ua[nops(ua)];
    // extract v and b from vb
        v := [op(vb, 1..nops(vb)-1)]; b := vb[nops(vb)];
    // the recursion formula
        dom::mapterms(dom::mult2Basis(ua, v), append, b) +
        dom::mapterms(dom::mult2Basis(u, vb), append, a) *
           q^nops(vb)
    end_proc;
end_domain:
   \end{Mexin}
   Note: in a free module, the entry \Mex{dom::basisIndices} contains
   the combinatorial class that indexes the basis of the module, and
   the function \Mex{mapterms(elts, f, ...)} applies \Mex{f} on each
   term of the element \Mex{elts} of the module. Thus, if \Mex{elts}
   writes $\sum_w c_w\,w$, the call
  \begin{Mvin}{prompt=,click=false,test=false}
      dom::mapterms(elts, append, b)
  \end{Mvin}
  \begin{Mvout}{test=false,hide=true}
  \end{Mvout}
returns the \mupad{} representation of $\sum_wc_w\,wb$.

Let us declare this algebra over the field of expressions:
  \begin{Mexin}
W := qShuffleAlgebra(Dom::ExpressionField()):
  \end{Mexin}
  \begin{Mvout}{hide=true}
  \end{Mvout}
and try some computations:
  \begin{Mexin}
W([a])*W([b]);
W([b])*W([a]);
  \end{Mexin}
  \begin{Mexout}
                    q W([b, a]) + W([a, b])

                    W([b, a]) + q W([a, b])
  \end{Mexout}
Obviously, this is a non commutative algebra. One can use any object
as letter:
  \begin{Mexin}
W([b, c, d])*W([2, 3])
  \end{Mexin}
  \begin{Mexout}
 3                       4
q  W([b, 2, c, 3, d]) + q  W([2, b, c, 3, d]) +

    2                       6
   q  W([b, c, 2, 3, d]) + q  W([2, 3, b, c, d]) +

    4                       5
   q  W([b, 2, 3, c, d]) + q  W([2, b, 3, c, d]) +

                         2
   W([b, c, d, 2, 3]) + q  W([b, 2, c, d, 3]) +

    3
   q  W([2, b, c, d, 3]) + q W([b, c, 2, d, 3])
  \end{Mexout}
Moreover, the automatic conversion from the base field allows one to write
complicated expression such as:
  \begin{Mexin}
1/2*W([b])^3 + W([a])*(1 + W([1, 2]))
  \end{Mexin}
  \begin{Mexout}
 2
q  W([1, 2, a]) + W([a, 1, 2]) + q W([1, a, 2]) +

   /               2      \
   | (q + 1) (q + q  + 1) |
   | -------------------- | W([b, b, b]) + W([a])
   \           2          /
  \end{Mexout}
Finally note that this implementation is not very efficient. In particular,
at each stage of the recursion in the expression:
\begin{Mvin}{prompt=,click=false,test=false}
  dom::mapterms(dom::mult2Basis(ua, v ), append, b) +
  dom::mapterms(dom::mult2Basis(u,  vb), append, a) * q^nops(vb)
\end{Mvin}
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
the system has to solve the overloading, i.e., to decide the meaning
of \Mex{+} and \Mex{*}. It is better to decide this once and for all,
i.e., to replace \Mex{+} by \Mex{dom::plus2}, and \Mex{*} by
\Mex{dom::multcoeffs}.
%\footnote{This \emph{programming style} fits within the more general
%  \emph{modular} style of the \caml{} community}.
The emerging expression is less readable, but its processing is
considerably faster:
\begin{Mvin}{prompt=,click=false,test=false}
  dom::plus2(dom::mapterms(dom::mult2Basis(ua, v ),
                           append, b),
       dom::multcoeffs(
             dom::mapterms(dom::mult2Basis(u,  vb),
                           append, a),
                       q^nops(vb)));
\end{Mvin}
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
Moreover, a non-recursive implementation of the $q$-shuffle is likely
to be more efficient.

\subsubsection{Sample applications}

We present here some typical applications that involve simultaneously
the combinatorial and the algebraic tools of \mupadcombinat{} together
with the general computer algebra tools of \mupad{}.

First, we find the minimal polynomial of an element of the group
algebra of the symmetric group of order $4$:
\begin{Mexin}
export(combinat):  
domain AlgSymGroup4
    inherits Dom::FreeModule(
                Dom::ExpressionField(),
                subClass(permutations, Parameters = 4));
    category Cat::AlgebraWithBasis(Dom::ExpressionField());

    basisName       := hold(p);
    exprTerm        := dom::exprTermIndex;
    one             := dom::term([1,2,3,4]);
    mult2Basis      := dom::term @ permutations::mult2;
end_domain:
x := AlgSymGroup4([2,3,4,1]):
y := x^0 + a1*x^1 + a2*x^2 + a3*x^3 + a4*x^4;
\end{Mexin}
\begin{Mexout}
a3 p[4, 1, 2, 3] + a2 p[3, 4, 1, 2] + a1 p[2, 3, 4, 1] +

   (a4 + 1) p[1, 2, 3, 4]
\end{Mexout}
\begin{Mexin}
solve([coeff(y)], [a1,a2,a3,a4]);
\end{Mexin}
\begin{Mexout}
              {[a1 = 0, a2 = 0, a3 = 0, a4 = -1]}
\end{Mexout}
\begin{Mexin}
subs(z^0 + a1*z^1 + a2*z^2 + a3*z^3 + a4*z^4, op(last(1),1))
\end{Mexin}
\begin{Mexout}
                                 4
                            1 - z
\end{Mexout}


Second, we use Pólya enumeration theory to count unlabelled non
oriented graphs on $n$ nodes without loops. To this end, we
build the symmetric group $S_n$ seen as the group of the permutations
of the $n$ nodes $\{i\}$ of the graphs, and the induced permutation
group $G_n$ on the set $E$ of the $\binom n 2$ possible edges
$\{i,j\}$ between those nodes:
\begin{Mexin}
S4 := Dom::SymmetricGroup(4):
G4 := Dom::PermutationGroupOnSets(S4, 2):
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
We compute next the cycle indicator of $G_4$. This is a symmetric
function which encodes the statistic of the cycle types of the
permutations in $G_4$:
\begin{Mexin}
Z4 := G4::cycleIndicator()
\end{Mexin}
\begin{Mexout}
1/24 p[1, 1, 1, 1, 1, 1] + 3/8 p[2, 2, 1, 1] + 1/3 p[3, 3] +

   1/4 p[4, 2]
\end{Mexout}
This is to be interpreted as follows: in $G_4$, there are $6=|G_4|\cdot\frac{1}{4}$
permutations with one cycle of length $4$ and one cycle of length $2$.
The interesting fact about this symmetric function is that, when
evaluated on an alphabet $A=(a_1,\dots,a_n)$, it returns the
generating series by weight for the functions from $E$ to a set of
size $n$ whose elements are weighted by $A$. For example, a graph can
be seen as a function from $E$ to a set with $2$ elements. Hence, the
total number of unlabelled graphs is given by:
\begin{Mexin}
Z4([1, 1])
\end{Mexin}
\begin{Mexout}
                              11
\end{Mexout}
whereas the generating series of unlabelled graphs on $4$ nodes by
number of edges is:
\begin{Mexin}
expand(Z4([1, q]))
\end{Mexin}
\begin{Mexout}
                    2      3      4    5    6
             q + 2 q  + 3 q  + 2 q  + q  + q  + 1
\end{Mexout}
Such computations are carried out in a rather efficient way, so that
e.g. counting the number of graphs with 20 nodes takes just a few
seconds:
\begin{Mexin}
(Dom::PermutationGroupOnSets(Dom::SymmetricGroup(20),
                             2))::cycleIndicator()([1, 1])
\end{Mexin}
\begin{Mexout}
            645490122795799841856164638490742749440
\end{Mexout}

If one is instead interested in counting multigraphs (graphs with
multiple edges) by number of edges, the cycle indicator polynomial can
be evaluated on the infinite alphabet $A:=(1,q,q^2,\dots)$. Infinite
alphabets are not yet directly supported by \mupadcombinat{}; however
this can easily be done by hand since the evaluation of the symmetric
powersum $p_k$ on the alphabet $A$ is obtained by encoding $A$ as
$1+q+q^2+\dots=\frac1{1-q}$ and substituting $q$ by $q^k$ in this
formula:
\begin{Mexin}
H4 := _plus(_mult(op(term, 1),
                  1/(1 - q^k) $ k in op(term, 2))
            $ term in poly2list(Z4))
\end{Mexin}
\begin{Mexout}
          3                 1                 1
-------------------- + ----------- + ------------------- +
    2     2        2             6       2        4
8 (q  - 1)  (q - 1)    24 (q - 1)    4 (q  - 1) (q  - 1)

        1
   -----------
       3     2
   3 (q  - 1)
\end{Mexout}

Now, the number of multigraphs with 0 to 4 edges can be obtained by
Taylor expansion:
\begin{Mexin}
series(H4, q, 5)
\end{Mexin}
\begin{Mexout}
                         2      3       4      5
              1 + q + 3 q  + 6 q  + 11 q  + O(q )
\end{Mexout}

In fact, this method is used to implement counting in the
combinatorial class \Mup{combinat::integerVectorsModPermutationGroup}:
\begin{Mexin}
M4:=combinat::integerVectorsModPermutationGroup(G4):
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
\begin{Mexin}
M4::generatingSeries(q)
\end{Mexin}
\begin{Mexout}
          3                 1                 1
-------------------- + ----------- + ------------------- +
    2     2        2             6       2        4
8 (q  - 1)  (q - 1)    24 (q - 1)    4 (q  - 1) (q  - 1)

        1
   -----------
       3     2
   3 (q  - 1)
\end{Mexout}
\begin{Mexin}
M4::count(i) $ i = 0..10
\end{Mexin}
\begin{Mexout}
           1, 1, 3, 6, 11, 18, 32, 48, 75, 111, 160
\end{Mexout}
%$

\subsubsection{Advanced algebraic structures}

The current development aims to provide a framework for advanced
algebraic structures, such as modules with several bases or Hopf
algebras, with plans for Lie algebras and operads in the long run. In
this section, we demonstrate how to implement such structures. At the
time of writing, the user interface is not fully stabilized, so please
check the latest available documentation before trying out the
examples.

We start with an example of algebra with several bases. Let $S$ be a
finite set, and consider the free module $M$ over the subsets of $S$.
It is endowed with an algebra structure by extending the intersection
operation by linearity. Implementing this algebra in \mupad{} requires
some helper tools; we put them inside a dummy domain called
\Mex{SubsetsSpaceTools} to avoid polluting the global name space:
\begin{Mexin}
domain SubsetsSpaceTools
    info_str := "Helper tools for the domain 'SubsetsSpace'";
end_domain:
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
We now implement the module $M$ with elements expanded on the
fundamental basis denoted by $F$.  There are two parameters: the set
\Mex{S} and, as usual, the coefficient ring \Mex{Ring}. Note the use
of \Mup{combinat::subClass} to define the combinatorial class of the
subsets of \Mex{S}:
\begin{Mexin}
domain SubsetsSpaceTools::Fundamental(S, Ring)
    category Cat::AlgebraWithBasis(Ring);
    inherits Dom::FreeModule(Ring,
                 combinat::subClass(combinat::subsets,
                                    Parameters = S));
    info_str := "The subset space on the fundamental basis";
    basisName := hold(F);

    mult2Basis :=
    proc(s1: dom::basisIndices, s2: dom::basisIndices)
    begin
        dom::term(s1 intersect s2);
    end_proc;
end_domain:
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
Let us just recall that, in a free module, the entry \Mex{dom::basisIndices}
contains the combinatorial class that indexes the bases of the module. Here,
this is a shortcut for the combinatorial class:
\begin{Mvin}{prompt=,click=false,test=false}
  combinat::subClass(combinat::subsets, Parameters = S)
\end{Mvin}
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
The module $M$ has two other bases $\operatorname{In}$ and
$\operatorname{Out}$ that we describe below. We just declare them to
\mupad{}, without implementing the product:
\begin{Mexin}
domain SubsetsSpaceTools::In(S, Ring)
    category Cat::AlgebraWithBasis(Ring);
    inherits Dom::FreeModule(Ring,
                 combinat::subClass(combinat::subsets,
                                    Parameters = S));
    info_str := "The subset space on the 'In' basis";
    basisName := hold(In);
end_domain:

domain SubsetsSpaceTools::Out(S, Ring)
    category Cat::AlgebraWithBasis(Ring);
    inherits Dom::FreeModule(Ring,
                 combinat::subClass(combinat::subsets,
                                    Parameters = S));
    info_str := "The subset space on the 'Out' basis";
    basisName := hold(Out);
end_domain:
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
The module $M$ is endowed with a scalar product which makes the fundamental
basis $F$ orthonormal. The $\operatorname{In}$ basis is then defined by the rule
\begin{displaymath}
  \operatorname{In}_S = \sum_{X \subset S} F_X,
\end{displaymath}
and the $\operatorname{Out}$ basis is the dual basis of
$\operatorname{In}$ with respect to the scalar product. This
information is sufficient to define mathematically all the bases
change in between $F$, $\operatorname{In}$, and $\operatorname{Out}$
by transposing and inverting matrices. The implementation follows the
same compact line:
\begin{Mexin}
domain SubsetsSpace(S : DOM_SET,
             Ring = Dom::Rational : DOM_DOMAIN)
    category Cat::ModuleWithSeveralBases(Ring);
    inherits Dom::BaseDomain;

    info_str := "The subsets space on various bases";

    Fundamental := SubsetsSpaceTools::Fundamental(S, Ring);
    F           := dom::Fundamental; // a shortcut
    In          := SubsetsSpaceTools::In(S, Ring);
    Out         := SubsetsSpaceTools::Out(S, Ring);

    // When possible, define automatically basis changes by
    // transposition or inversion of matrices.
    autoDefineBasisChanges := TRUE;

    basisChangesBasis := table(
        (dom::In, dom::F) = 
            proc(set : dom::In::basisIndices) : dom::F
                local xSet;
            begin
                dom::F::plus(dom::F::term(xSet) $
                     xSet in combinat::subsets::list(set));
            end_proc);

    dual := dom; // The dual of this space.
// The pairs of dual bases.
// The pair [dom::Out, dom::In] will be automatically declared.
    dualBasesPairs := {[dom::F, dom::F], [dom::In, dom::Out]};

end_domain:
\end{Mexin}
% $
\begin{Mvout}{hide=true}
\end{Mvout}
The crucial line of the preceding code is the declaration of
\Mex{SubsetsSpace} as a \Mup{Cat::ModuleWithSeveralBases}.  This category
provides helper tools for implementing modules which are represented on
several modules. We just need to supply the basis changes from \Mex{In} to
\Mex{F} (see \Mex{basisChangesBasis}) and to declare which bases are in
duality (see \Mex{dual} and \Mex{basisChangesBasis}). The system then provides
default implementations for the scalar products and the other changes of bases
(see \Mex{autoDefineBasisChanges}), and provides the standard free module
entries \Mex{testtype} and \Mex{coeffRing} together with the set of bases
\Mex{bases}.

We define the free module spanned by the subsets of $\{1,2,3,4\}$ and
build some of its elements:
  \begin{Mexin}
M1234 := SubsetsSpace({1, 2, 3, 4}):
el1   := M1234::F({1, 2});
el2   := M1234::In({1, 2})
  \end{Mexin}
  \begin{Mexout}
                           F({1, 2})

                          In({1, 2})
  \end{Mexout}
The type checking works as usual:
  \begin{Mexin}
testtype(el1, M1234), testtype(el2, M1234)
  \end{Mexin}
  \begin{Mexout}
                          TRUE, TRUE
  \end{Mexout}
as well as the bases changes:
  \begin{Mexin}
M1234::In(el1)
  \end{Mexin}
  \begin{Mexout}
           - In({2}) - In({1}) + In({}) + In({1, 2})
  \end{Mexout}
  \begin{Mexin}
M1234::Out(el2)
  \end{Mexin}
  \begin{Mexout}
4 Out({1, 2, 3, 4}) + 2 Out({2, 3, 4}) + 2 Out({1, 3, 4}) +

   4 Out({1, 2, 4}) + 4 Out({1, 2, 3}) + Out({3, 4}) +

   2 Out({2, 4}) + 2 Out({2, 3}) + 2 Out({1, 4}) +

   2 Out({1, 3}) + Out({4}) + Out({3}) + 2 Out({2}) +

   2 Out({1}) + Out({}) + 4 Out({1, 2})
  \end{Mexout}
  The required matrix inversions are computed only once and
  remembered, so that later basis changes are considerably faster, at
  some memory cost.

Finally we check that algebra products and scalar products are
handled correctly:
  \begin{Mexin}
el1*el2
  \end{Mexin}
  \begin{Mexout}
              F({2}) + F({1}) + F({}) + F({1, 2})
  \end{Mexout}
  \begin{Mexin}
operators::scalar(el1, el2)
  \end{Mexin}
  \begin{Mexout}
                               1
  \end{Mexout}
Products of \Mex{Out} elements are actually computed and returned in
the \Mex{F} basis. As usual, an explicit conversion can be used to
force the result back in the \Mex{Out} basis:
  \begin{Mexin}
M1234::Out({1, 3, 4})*M1234::Out({2, 3});
  \end{Mexin}
  \begin{Mexout}
- F({1, 2, 3, 4}) + F({2, 3, 4}) + F({1, 3, 4}) +

   F({1, 2, 3}) - F({3, 4}) - F({2, 3}) - F({1, 3}) + F({3})
  \end{Mexout}
  \begin{Mexin}
M1234::Out(last(1))
  \end{Mexin}
  \begin{Mexout}
                           Out({3})
  \end{Mexout}

Let us finish this tour by showing a small example of Hopf algebra: the free
algebra over the integers, those being primitive for the coproduct
(non commutative symmetric functions on one of the powersum bases):
  \begin{Mexin}
domain FreeAlgebraInteger
    inherits Dom::FreeModule(Dom::Rational,
                             combinat::compositions);
    category Cat::GradedHopfAlgebraWithBasis(Dom::Rational);

    basisName       := hold(P);
    exprTerm        := dom::exprTermIndex;
    one             := dom::term([]);
    mult2Basis      := dom::term @ _concat;
    coproductBasis  :=
    proc(compo : dom::basisIndices)
        local i, tens;
    begin
        tens := dom::tensorSquare;
        tens::mult(tens::plus2(tens::term([[i], []]),
                               tens::term([[],  [i]]))
                      $ i in compo);           
    end_proc;
end_domain:
alias(NCSF = FreeAlgebraInteger)
  \end{Mexin}
% $ 
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
Here is a sample coproduct computation:
\begin{Mexin}
tens := operators::coproduct(NCSF([2, 1, 3]))
\end{Mexin}
\begin{Mexout}
tensor(P[2, 3], P[1]) + tensor(P[1, 3], P[2]) +

   tensor(P[2, 1], P[3]) + tensor(P[3], P[2, 1]) +

   tensor(P[1], P[2, 3]) + tensor(P[2], P[1, 3]) +

   tensor(P[2, 1, 3], P[]) + tensor(P[], P[2, 1, 3])
\end{Mexout}
To improve the readability, we use \Mex{ø} (iso-latin-1 character of
code 248) as symbol for the tensor product:
\begin{Mexin}
operators::setTensorSymbol("ø"):
tens
\end{Mexin}
\begin{Mexout}
P[2, 3] ø P[1] + P[1, 3] ø P[2] + P[2, 1] ø P[3] +

   P[3] ø P[2, 1] + P[1] ø P[2, 3] + P[2] ø P[1, 3] +

   P[2, 1, 3] ø P[] + P[] ø P[2, 1, 3]
\end{Mexout}
\Mex{ø} can be use as well to type in tensor products:
\begin{Mexin}
NCSF([1,2]) ø NCSF([1])
\end{Mexin}
\begin{Mexout}
                       P[1, 2] ø P[1]
\end{Mexout}

The product of \Mex{NCSF} is naturally extended to $\Mex{NCSF}\otimes
\Mex{NCSF}$, so that we can compute expressions such as:
\begin{Mexin}
  tens * (NCSF([1,2]) ø NCSF([1]))
\end{Mexin}
\begin{Mexout}
P[2, 1, 3, 1, 2] ø P[1] + P[2, 1, 2] ø P[1, 3, 1] +

   P[1, 1, 2] ø P[2, 3, 1] + P[3, 1, 2] ø P[2, 1, 1] +

   P[2, 1, 1, 2] ø P[3, 1] + P[1, 3, 1, 2] ø P[2, 1] +

   P[2, 3, 1, 2] ø P[1, 1] + P[1, 2] ø P[2, 1, 3, 1]
\end{Mexout}
Note that a new domain representing the tensor square has been
automatically created:
\begin{Mexin}
domtype(tens)
\end{Mexin}
\begin{Mexout}
         Dom::TensorProductOfFreeModules([NCSF, NCSF])
\end{Mexout}

Since \Mex{NCSF} is a graded connected bi-algebra, it is automatically
a Hopf algebra, whose antipode can be computed recursively (in a slow
way):
  \begin{Mexin}
operators::antipode(NCSF([2, 1, 3]))
  \end{Mexin}
  \begin{Mexout}
                        (-1) P[3, 1, 2]
\end{Mexout}
Of course, in the case of \Mex{NCSF}, it would have been much more
efficient to implement the direct combinatorial formula for the
antipode:
\begin{Mvin}{prompt=,click=false,test=false}
    antipodeBasis :=
        comp -> dom::monomial(-1^nops(comp), revert(comp));
\end{Mvin}
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
Another very useful feature is the possibility to define tensor
product of maps:
\begin{Mexin}
idTensorAntipode := operators::tensorProductOfMaps(
    [id, NCSF::antipode],
    NCSF::tensorSquare,
    NCSF::tensorSquare):
idTensorAntipode(tens)
\end{Mexin}
\begin{Mexout}
- P[2, 3] ø P[1] - P[1, 3] ø P[2] - P[2, 1] ø P[3] +

   P[3] ø P[1, 2] + P[1] ø P[3, 2] + P[2] ø P[3, 1] +

   P[2, 1, 3] ø P[] - P[] ø P[3, 1, 2]
\end{Mexout}
We conclude by using this feature to check, on some examples, that the
antipode is correct:
  \begin{Mexin}
es := NCSF::mu @ idTensorAntipode @ NCSF::coproduct:
  \end{Mexin}
\begin{Mvout}{test=false,hide=true}
\end{Mvout}
  \begin{Mexin}
es(NCSF([2, 1]));
es(NCSF([]));
  \end{Mexin}
  \begin{Mexout}
                               0

                              P[]
  \end{Mexout}

\subsection{Current features}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We conclude this guided tour by a summary of the current features. A
first part of the package consists of predefined libraries to count,
enumerate, and manipulate standard combinatorial objects (partitions,
compositions, sets, words, permutations, tableaux, trees, \dots),
together with generic tools to help define new combinatorial classes:
\begin{itemize}
\item A computational engine for dealing with integer vectors with
  prescribed constraints (monomials, compositions, partitions, Dyck
  paths, \dots)
\item A computational engine for generating linear extensions of
  posets (standard young tableaux, standard ribbons, \dots)
\item A refactored and extended version of the former \texttt{CS}
  library by S.~Corteel, A.~Denise, I.~Dutour, and P.~Zimmermann to
  deal with objects defined by a recursive grammar.
\end{itemize}
Most predefined libraries actually make use of these engines.

A second part consists of tools to build combinatorial algebras. The
typical usage is to take a vector space with basis indexed by some
combinatorial objects, to define a product for two basis elements and
to extend the product by bilinearity. The system automatically takes
care of the data structure of algebraic elements, of extensions of
functions by linearity, bi-linearity, or associativity, of conversions
between different bases, etc. Similarly, one may define coproducts,
antipodes, and similar operators, to implement more involved structures
such as Hopf algebras. Some preliminary work has been done to
manipulate Lie algebras and operads as well. In short, the system
takes care of the algebraic bookkeeping, so that one can concentrate
on the underlying combinatorics rather than on the programming.

As examples of usage and applications, we provide a library for the
algebra of symmetric functions, and we have (currently undocumented)
libraries for the algebra of non commutative symmetric functions, the
algebra of (free) quasi-symmetric functions, the Loday-Ronco algebra,
the Weyl algebra, the rational Steenrod algebra, the type-A Hecke and
Hecke-Clifford algebras, as well as invariant rings of permutation
groups, and group algebras.

In the future \ifcolloquial (or near future if you help us!)\fi we plan
to provide predefined libraries for the free symmetric algebra, the
algebra of matrix quasi symmetric functions, the descents and peaks
algebras, general Ore-algebras, the symmetric Weyl algebra, the
algebra of multi-symmetric functions, the divided power algebra, free
Lie algebras, etc.

Finally, we provide libraries for manipulating weighted automatons
and related (tropical) semi-rings.

%%// Compatibilité avec mu-EC
%%export(muEC);
%%PART::ListPart(3);
%%SYMF::Tom(s[3,2,1])
%% thanks:=output::asciiArt(["Thanks"])^(2*output::asciiArt(["all of you!"]));

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