\section{Exercises}

In the exercises below, we assume that the package has been loaded
with:
\begin{Mvin}{test=false}
package("Combinat"):
\end{Mvin}

Also, to save some typing, we recommend to export the combinat
library:
\begin{Mexin}
export(combinat):
\end{Mexin}

\newtheorem{correction*}{Correction\\}
\newif\ifcorrection
\correctiontrue

\subsection{Using existing combinatorial classes}

\begin{exercise}
  \begin{enumerate}
  \item List all the strict partitions of $5$. Hint: use
    \Mup{combinat::partitions::list} with \Mex{MaxSlope}.
  \item List all the vectors of $0$ and $1$ of length $5$. Hint: use
    \Mup{combinat::integerVectors::list} with \Mex{MaxPart}; also try
    out \Mex{i^3 $ i=1..5}, and use \Mup{_concat}. %$
  \end{enumerate}
\end{exercise}
\ifcorrection
\begin{correction*}
  \begin{Mexin}
combinat::partitions::list(5, MaxSlope = -1)
  \end{Mexin}
  \begin{Mexout}
                     [[5], [4, 1], [3, 2]]
  \end{Mexout}
\end{correction*}
\fi

\begin{exercise}
  Pretty print all the Dyck paths of length $6$. Hint: use \Mup{map},
  \Mup{combinat::dyckWords::list}, and
  \Mup{combinat::dyckWords::printPretty}.
\end{exercise}

\begin{exercise}
  List all the Motzkin paths of length $6$ (a Motzkin path is similar
  to a Dyck path, except that horizontal steps are allowed). Hint: use
  \Mex{combinat::integerVectors}.
\end{exercise}

\begin{exercise}
  Pretty print all the tableaux of size $4$. Hint: use
  \Mup{combinat::partitions::list}, \Mup{combinat::tableaux::list} and
  \Mup{combinat::tableaux::printPretty}.
\end{exercise}

\begin{exercise}
  Count the number of partitions of $1000$ with parts bounded below by
  $10$. Hint: first try out how far you can go with
  \Mup{combinat::partitions}. Then, switch to
  \Mup{combinat::decomposableObject} and use \Mex{Multiset},
  \Mex{Sequence}, and \Mex{MinLength}. Finally, optimize your grammar
  by implementing the combinatorial class of integers $\geq 10$. Hint:
  check the examples of use of \Mup{combinat::decomposableObject} in
  the guided tour.
\end{exercise}

\subsection{Using generators}

\begin{exercise}
  Try and analyze the following piece of code:
  \begin{Mexin}
g := combinat::partitions::generator(4):
while (p := g()) <> FAIL do
  print(p, combinat::partitions::printPretty(p))
end_while
  \end{Mexin}
  \begin{Mvout}{hide}
                         +---+---+---+---+
                    [4], |   |   |   |   |
                         +---+---+---+---+

                             +---+
                             |   |
                             +---+---+---+
                     [3, 1], |   |   |   |
                             +---+---+---+

                               +---+---+
                               |   |   |
                               +---+---+
                       [2, 2], |   |   |
                               +---+---+

                                +---+
                                |   |
                                +---+
                                |   |
                                +---+---+
                     [2, 1, 1], |   |   |
                                +---+---+

                                    +---+
                                    |   |
                                    +---+
                                    |   |
                                    +---+
                                    |   |
                                    +---+
                      [1, 1, 1, 1], |   |
                                    +---+

                             FAIL
  \end{Mvout}
\end{exercise}

\begin{exercise}
  \begin{enumerate}
  \item Analyze the following piece of code:
  \begin{Mexin}
makeGenerator :=
proc()
    option escape;
    local i;
begin
    i := 0;
    proc() begin i:=i+1; end;
end:
g:=makeGenerator():
g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mvout}{hide}
                         1, 2, 3, 4, 5
  \end{Mvout}
\item Modify this piece of code to build a generator for the cube
  powers of integers: \Mex{1, 8, 27, \Mseq{}}
\item Write a function that takes a power $p$ and returns a generator
  for all the $p$-th powers of integers.
\item Reimplement those generators using the functions
  \Mup{combinat::generators::fromNext} and
  \Mup{combinat::generators::map}.
\end{enumerate}
\end{exercise}

\begin{exercise}
  \begin{enumerate}
  \item Build a generator for all the standard tableaux of size $4$.
    Hint: use \Mup{combinat::generators::pipe}.
  \item Build a generator for all the standard tableaux of any size.
  \item Write a function of one argument \Mex{n} which returns a
    generator for all the Motzkin words of length \Mex{n}. Hint: use
    closures and don't forget the escape option.
  \end{enumerate}
\end{exercise}

\begin{exercise}
  \begin{enumerate}
  \item
    \begin{sloppypar}
      Compute the average number of inversions among all the
      permutations of $n=7$ that avoid the pattern \Mex{[1,4,3,2]}.
      Hint: use \Mup{combinat::permutations::inversionsNumber} and
      \Mup{combinat::permutations::hasPattern}, and try out the
      following example:
    \end{sloppypar}
    \begin{Mexin}
select([1,2,3,4,5,6,7,8], not isprime);
    \end{Mexin}
    \begin{Mvout}{hide}
                         [1, 4, 6, 8]
    \end{Mvout}
    Evaluate the complexity in time and memory of this computation.
  \item Compute the same thing with a memory complexity of $O(n)$.
    Hint: use generators, \Mup{combinat::generators::select}, and try
    out this example:
    \begin{Mexin}
makeAverager :=
proc()
    option escape;
    local sum,n;
begin
    sum:=0;
    n:=0;
    proc(x)
    begin
        if args(0) = 0 then	// call without argument
            sum/n
        else
            sum := sum + x;	// call with one argument
            n := n + 1;
        end_if;
    end_proc;
end_proc:
g := makeAverager():    // create a new averager
g(1), g(5), g(0), g(10):   // accumulate the numbers
g();			// return their average
    \end{Mexin}
    \begin{Mvout}{hide}
                               4
    \end{Mvout}
  \end{enumerate}
\end{exercise}

\ifcorrection
\begin{correction*}
\begin{Mvin}{test=false}
export(combinat):
N:=6:
// Brute force solution
averager := makeAverager():
time(map(select(permutations(N), not permutations::hasPattern, [1,4,3,2]),
         averager@permutations::inversionsNumber));
float(averager());
// Solution using generators:
averager := makeAverager():
time(generators::consume(
    generators::map(
        generators::select(
	    permutations::generator(N),
            not permutations::hasPattern, [1,4,3,2]),
        averager@permutations::inversionsNumber)));
float(averager())
\end{Mvin}
\begin{Mvout}{test=false}
                             1260

                          7.582846004

                             1277

                          7.582846004
\end{Mvout}
\end{correction*}
\fi

\subsection{Implementing new algebras}

\begin{exercise}
  \begin{enumerate}
  \item Implement the algebra \Mex{SetAlgebra} whose basis is indexed
    by sets and product given by the union of sets.  Hint: look for
    the implementation of \Mex{FreeAlgebra} in the guided tour, use
    \Mup{combinat::subsets} as combinatorial class, and see
    \Mex{?_union}.
  \item Implement the natural morphism  from \Mex{FreeAlgebra} to
    \Mex{SetAlgebra} which sends \Mex{[a,c,a,a,b,c]} to \Mex{\{a,b,c\}}.
  \end{enumerate}
\end{exercise}



\begin{exercise}
  \begin{enumerate}
  \item Implement the shuffle algebra \Mex{ShuffleAlgebra} on
    compositions. Hint: look for the implementation of
    \Mex{FreeAlgebra} in the guided tour, use
    \Mup{combinat::words::shuffle}, and try out
    \begin{Mexin}
_plus(x^i $ i in [1,5,6,8])
    \end{Mexin} %$
    \begin{Mvout}{hide}
                        8    6    5
                       x  + x  + x  + x
    \end{Mvout}
  \item Implement a function \Mex{coconcat(u)} that returns the list
    of all the couples of words $v$ and $w$ such that $u=v.w$:
  \begin{Mvin}{test=false}
coconcat([1, 2, 3])
  \end{Mvin}
  \begin{Mvout}{test=false}
[[[], [1, 2, 3]], [[1], [2, 3]], [[1, 2], [3]], [[1, 2, 3], []]

   ]
  \end{Mvout}
  \item Make the shuffle algebra into a Hopf algebra (category
    \Mex{Cat::HopfAlgebraWithBasis}) by inserting the following
    method:
    \begin{Mexin}
coproductBasis :=
proc(u: words) : ShuffleAlgebra
    local v;
begin
    _plus(dom::tensorSquare::term(v) $ v in coconcat(u))
end_proc:
    \end{Mexin} %$
    \begin{Mvout}{hide}
    \end{Mvout}
    You can now compute the coproduct of any element of the algebra
    using \Mup{operators::coproduct}, and reciprocally use
    \Mup{operators::mu} to compute the image in \Mex{ShuffleAlgebra}
    of any element of $S\otimes S$ via the product. You may wish to
    issue:
    \begin{Mvin}{test=false}
export(operators, coproduct, mu):
    \end{Mvin}
    \begin{Mvout}{hide, test=false}
    \end{Mvout}
  \item Use this to check, on some examples, that this is indeed a Hopf
    algebra; that is that the product and coproduct are compatible.
  \item Add the missing implementations for the counit and the antipode
    of the Hopf algebra.
  \item Add a degree method to make \Mex{ShuffleAlgebra} into a graded
    Hopf algebra (\Mex{Cat::GradedHopfAlgebraWithBasis}), and write a
    procedure that checks systematically the compatibility of the
    product and coproduct up to a given degree.
  \end{enumerate}
\end{exercise}

\ifcorrection
\begin{correction*}
\eng{This is the \Mup{coconcat} function:}
\begin{Mexin}
coconcat := proc(l) local i; begin [ [[op(l,1..i)], [op(l, i+1..nops(l))]] $ i = 0 .. nops(l)] end:
prog::test(coconcat([a, b, b, c]),
           [[[], [a, b, b, c]], [[a], [b, b, c]], [[a, b], [b, c]], [[a, b, b], [c]], [[a, b, b, c], []]]):
prog::test(coconcat([]),
           [[[], []]]):
prog::test(coconcat([a]),
           [[[], [a]], [[a], []]]):
\end{Mexin} %$
  \begin{Mvout}{hide}
  \end{Mvout}
  \eng{We check its behavior:}
  \begin{Mexin}
coconcat([1, 2, 3])
  \end{Mexin}
  \begin{Mexout}
[[[], [1, 2, 3]], [[1], [2, 3]], [[1, 2], [3]], [[1, 2, 3], []]

   ]
  \end{Mexout}
  \eng{Here is now the full featured code for the shuffle algebra:}
  \begin{Mexin}
domain ShuffleAlgebra
    inherits Dom::FreeModule(Dom::Rational, combinat::words);
    category Cat::GradedHopfAlgebraWithBasis(Dom::Rational);

    degreeBasis   := nops;

    one           := dom::term([]);

    mult2Basis    :=
    proc(t1,t2)
    begin
        _plus(dom::term(v) $ v in combinat::words::shuffle(t1,t2));
    end;

    coproductBasis :=
    proc(u: dom::basisIndices) : dom::tensorSquare
        local v;
    begin
        _plus(dom::tensorSquare::term(v) $ v in coconcat(u))
    end_proc;
end_domain:
  \end{Mexin}
  \eng{Some sample computations:}
  \begin{Mexin}
ShuffleAlgebra([1, 2, 3])*ShuffleAlgebra([4, 5])
  \end{Mexin}
  \begin{Mexout}
B([4, 5, 1, 2, 3]) + B([4, 1, 5, 2, 3]) + B([4, 1, 2, 5, 3]) +

   B([4, 1, 2, 3, 5]) + B([1, 4, 5, 2, 3]) +

   B([1, 4, 2, 5, 3]) + B([1, 4, 2, 3, 5]) +

   B([1, 2, 4, 5, 3]) + B([1, 2, 4, 3, 5]) + B([1, 2, 3, 4, 5])
  \end{Mexout}

  \begin{Mexin}
export(operators, coproduct):
a:=ShuffleAlgebra([1,2,3]): b:=ShuffleAlgebra([4,5]):
coproduct(a)*coproduct(b) - coproduct(a*b)
  \end{Mexin}
  \begin{Mexout}
                               0
  \end{Mexout}

\end{correction*}
\fi

%% write a recursive function that returns all the motzkin paths of length $n$
%% build a generator for all the integer partitions
%% build a generator for all the strict integer partitions
%% build a generator for all the integer partitions such that ...
%% build a generator for all the vector partitions of a given size
%% (integer matrices up to a permutation of the columns)
%% build a domain for those vector partitions
%% write a domain for motzkin paths
%% write a generator for all arrangements of size k of a permutation
%% write a generator for all permutations with a given cycle type
%% write the domain combinat::permutations::fromCycleType, with count, ...
%% write a generator for skew partitions using integerListsLexTools
%% write a generator for skew tableaux
%% write the documentation for all of those


%\begin{exercise}
%  Define the combinatorial class of prime integers.
%\end{exercise}

%\begin{correction*}
%% domain primeInteger
%%     category Cat::CombinatorialClass;

%%     count := n->if isprime(n) then 1 else 0; end;
%%     list  := n->if isprime(n) then [n] else []; end;
%%     random := n->if isprime(n) then n else FAIL; end;
%%     unrank := (i,n)->if isprime(n) and i=1 then n else FAIL; end;
%% end:
%% bla:=combinat::decomposableObjects([S=Multiset(Domain(primeInteger))]):
%\end{correction*}


% split a list into consecutive blocs of length c[1],...,c[k]
% r:=1 [ [op(l, r..(r:=r+i)-1)] $ i in c] ;

\subsection{The degenerate Hecke Algebra}
\eng{ The Iwahori-Hecke algebra $H_n(q)$ is the ${\mathbb C}$-algebra
  generated by elements $T_i$ for $i<n$ with the relations:
\begin{alignat}{2}
  T_i^2&=(q-1)T_i+q    \qquad&&\text{for $1\leq i \leq n-1$,}\notag\\
  T_iT_j&=T_jT_i \qquad&&\text{for $|i-j|>1$,}\\
  T_iT_{i+1}T_i &=T_{i+1}T_iT_{i+1}T \qquad&&\text{for $1\leq i \leq n-2$,}
  \notag
\end{alignat}
The $0$-Hecke algebra is obtained by setting $q=0$ in these relations. Then,
the first relation becomes $T_i^2=-T_i$. Let $\pi_i := 1+T_i$. 
\begin{enumerate}
\item Use \Mex{combinat::subClass} to define the combinatorial class
  of the permutations of $n$.
\item Define a parameterized domain \Mex{HeckePi(n)} for the Hecke algebra
  in the basis $(\pi_\sigma)_{\sigma \in {\mathfrak S}_n}$ with coefficient
  the rational (\Mup{Dom::Rational}).
\item Define the elementary generator $\pi_i$. Check some braid
relations. 
\item Define a parameterized domain \Mex{HeckeT(n)} for the Hecke algebra
  in the basis $(T_\sigma)_{\sigma \in {\mathfrak S}_n}$ with coefficient
  the rational (\Mup{Dom::Rational}).
\item Check for small $n$ that sum and alternating sum of the $T_\sigma$ are
two idempotents.
\item Define the change of basis between the two versions. This can be done by
  hands or using the Bruhat order (\Mex{permutations::smallerBruhat}). Make
  the conversion automatic.
\item We need to compute with different coefficients, in particular we often
need to compute with unknown coefficients taken out
\Mupc{Dom::ExpressionField}{}. Modify the two parameterized domains
\Mex{HeckePi(n)} and \Mex{HeckeT(n)} so that they accept a ring for second
parameter with \Mupc{Dom::ExpressionField}{} as default value.
\end{enumerate}
As a application we want now to compute the radical of $Hn(0)$. We use a
characterization from Dickson.
\newtheorem{theorem}{Theorem}[section]
\begin{theorem}
  Let $A$ be a sub algebra of $M_n(F)$ for a field $F$ of zero characteristic.
  Then $x\in A$ is in the radical of $A$ if and only if the trace of each $y$
  in the two sided (resp. left, right) ideal generated by $x$ ($AxA$, resp.
  $Ax$, $xA$) is zero.
\end{theorem}
For finite dimensional algebra $A$, we realize $A$ as a matrix algebra by
considering any faithful representation, for example the regular one. 
\begin{enumerate}
\item Let $g := \sum_{\sigma \in {\mathfrak S}_n} a_\sigma \Pi_{\sigma}$ be
  the generic element of $H_n(0)$. Compute $g$ and the generating family
  $(g\Pi_{\mu})_{\mu \in {\mathfrak S}_n}$ for the ideal.
\item Write a function \Mex{trace} that compute the trace of the endomorphism
$x\in Hn(0) \to x e$ where $e\in Hn(0)$.
\item Using Dickson criterion, compute the equation of the radical of $Hn(0)$.
\item What is the dimension of the radical, of the quotient ?
\item Write a function \Mex{radNormal} that normalize an element of $H_n(0)$
  modulo its radical.
\end{enumerate}
Suppose that $A$ is an algebra with a basis $B$. In \mupad, $A$ is a
certain domain \Mex{Alg}. The basis $B$ of $A$ is indexed by the element of
the domain \Mex{Alg::basisIndices}. Like all combinatorial domain this domain may
have a list method which can be called by \Mex{Alg::basisIndices::list}.  
\begin{enumerate}
\item Write a function \Mex{GetBasis} to compute a basis of an algebra or more
generally of a free module.
\item Write a function \Mex{Generic Element} to compute a generic element;
\item Write a function \Mex{Radical} to compute the radical of an algebra. 
\end{enumerate}

}

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