1. Exercises

In the exercises below, we assume that the package has been loaded with:


Also, to save some typing, we recommend to export the combinat library:



1.1. Using existing combinatorial classes

  1. List all the strict partitions of math. Hint: use combinat::partitions::list with MaxSlope.    

  2. List all the vectors of math and math of length math. Hint: use combinat::integerVectors::list with MaxPart; also try out i^3 $i=1..5, and use _concat.  

  3. Pretty print all the Dyck paths of length math. Hint: use map, combinat::dyckWords::list, and combinat::dyckWords::printPretty.

  4. List all the Motzkin paths of length math (a Motzkin path is similar to a Dyck path, except that horizontal steps are allowed). Hint: use combinat::integerVectors.

  5. Pretty print all the tableaux of size math. Hint: use combinat::partitions::list, combinat::tableaux::list and combinat::tableaux::printPretty.

  6. Count the number of partitions of math with parts bounded below by math. Hint: first try out how far you can go with combinat::partitions. Then, switch to combinat::decomposableObjects and use the constructors Multiset and Sequence with the MinLength and MaxLength options. Finally, optimize your grammar by implementing a combinatorial class for math. Hint: check the examples of use of combinat::decomposableObjects in the guided tour.

  7. Count how many distinct expressions can be built from the variables {x, y, z} and two binary operators f and g, with 10 variables altogether. Hint: use combinat::decomposableObjects, with the constructors Atom,Epsilon,Prod,Union. Then, display those with 3 and 4 variables. Improve the pretty printing using either a substitution, or the Alias constructor.

1.2. Using generators

Try and analyze the following piece of code:

g := combinat::partitions::generator(4):

while (p := g()) <> FAIL do

  print(p, combinat::partitions::printPretty(p))



Analyze the following piece of code:

makeGenerator :=


    option escape;

    local i;


    i := 0;

    proc() begin i:=i+1; end;



g(), g(), g(), g(), g()


Modify it to build a generator for the cube powers of integers: 1, 8, 27, ... 

Write a function that takes a power math and returns a generator for all the math-th powers of integers.

Reimplement those generators using the functions combinat::generators::fromNext and combinat::generators::map.

Build a generator for all the standard tableaux of size math. Hint: use combinat::generators::pipe.

Build a generator for all the standard tableaux of any size.

Write a function of one argument n which returns a generator for all the Motzkin words of length n. Hint: use closures and don't forget the escape option.

Compute the average number of inversions among all the permutations of math that avoid the pattern [1,4,3,2]. Hint: use combinat::permutations::inversionsNumber and combinat::permutations::hasPattern, and try out the following example:

select([1,2,3,4,5,6,7,8], not isprime);

Evaluate the complexity in time and memory of this computation.

Compute the same thing with a memory complexity of math. Hint: use generators, combinat::generators::select, and try out this example:

makeAverager :=


    option escape;

    local sum,n;






        if args(0) = 0 then // call without argument



            sum := sum + x; // call with one argument

            n := n + 1;




g := makeAverager():    // create a new averager

g(1), g(5), g(0), g(10):   // accumulate the numbers

g(); // return their average


1.3. Implementing new algebras

1.3.1. The set algebra

Implement the algebra SetAlgebra whose basis is indexed by sets and product given by the union of sets. Hint: look for the implementation of FreeAlgebra in the guided tour, use combinat::subsets as combinatorial class, and see ?_union.

Implement the natural morphism from FreeAlgebra to SetAlgebra which sends [a,c,a,a,b,c] to {a,b,c}.

1.3.2. The shuffle Hopf algebra

Implement the shuffle algebra ShuffleAlgebra on compositions. Hint: look for the implementation of FreeAlgebra in the guided tour, use combinat::words::shuffle, and try out

_plus(x^i $ i in [1,5,6,8])


Implement a function coconcat(u) that returns the list of all the couples of words math and math such that math:

coconcat([1, 2, 3])



Make the shuffle algebra into a Hopf algebra (category Cat::HopfAlgebraWithBasis) by inserting the following method:

coproductBasis :=

proc(u: words) : ShuffleAlgebra

    local v;


    _plus(dom::tensorSquare::term(v) $ v in coconcat(u))


   You can now compute the coproduct of any element of the algebra using operators::coproduct, and reciprocally use operators::mu to compute the image in ShuffleAlgebra of any element of math via the product. You may wish to issue:

export(operators, coproduct, mu):


Use this to check, on some examples, that this is indeed a Hopf algebra; that is that the product and coproduct are compatible.

Add the missing implementations for the counit and the antipode of the Hopf algebra.

Add a degree method to make ShuffleAlgebra into a graded Hopf algebra (Cat::GradedHopfAlgebraWithBasis), and write a procedure that checks systematically the compatibility of the product and coproduct up to a given degree. Correction

coconcat := proc(l) local i; begin [ [[op(l,1..i)], [op(l, i+1..nops(l))]] $ i = 0 .. nops(l)] end:

We check its behavior:

coconcat([1, 2, 3])

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], []]]):


           [[[], []]]):


           [[[], [a]], [[a], []]]):


Here is now the full featured code for the shuffle algebra:

domain ShuffleAlgebra

    inherits Dom::FreeModule(Dom::Rational, combinat::words);

    category Cat::GradedHopfAlgebraWithBasis(Dom::Rational);


     degreeBasis   := nops;


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


     mult2Basis    :=



        _plus(dom::term(v) $ v in combinat::words::shuffle(t1,t2));



     coproductBasis :=

    proc(u: dom::basisIndices) : dom::tensorSquare

        local v;


        _plus(dom::tensorSquare::term(v) $ v in coconcat(u))



Some sample computations:

ShuffleAlgebra([1, 2, 3])*ShuffleAlgebra([4, 5])


export(operators, coproduct):

a:=ShuffleAlgebra([1,2,3]): b:=ShuffleAlgebra([4,5]):

coproduct(a)*coproduct(b) - coproduct(a*b)


1.4. The degenerate Hecke Algebra

The Iwahori-Hecke algebra math is the math-algebra generated by elements math for math with the relations:


The math-Hecke algebra is obtained by setting math in these relations. Then, the first relation becomes math. Let math.

  1. Use combinat::subClass to define the combinatorial class of the permutations of math.

  2. Define a parameterized domain HeckePi(n) for the Hecke algebra in the basis math over the rational numbers (Dom::Rational).

  3. Define the elementary generator math. Check some braid relations.

  4. Define a parameterized domain HeckeT(n) for the Hecke algebra in the basis math over the rational numbers (Dom::Rational).

  5. Check for small math that sum and alternating sum of the math are two idempotents.

  6. Define the change of basis between the two versions. This can be done by hands or using the Bruhat order (combinat::permutations::smallerBruhat). Make the conversion automatic.

  7. We need to compute with different coefficients, in particular we often need to compute with unknown coefficients taken out Dom::ExpressionField(). Modify the two parameterized domains HeckePi(n) and HeckeT(n) so that they accept a ring for second parameter with Dom::ExpressionField() as default value.

As a application we want now to compute the radical of math. We use a characterization from Dickson.  Let math be a sub algebra of math for a field math of zero characteristic. Then math is in the radical of math if and only if the trace of each math in the two sided (resp. left, right) ideal generated by math (math, resp. math, math) is zero. For finite dimensional algebra math, we realize math as a matrix algebra by considering any faithful representation, for example the regular one.

  1. Let math be the generic element of math. Compute math and the spanning family math for the ideal it generates.

  2. Write a function trace that compute the trace of the endomorphism math where math.

  3. Using Dickson criterion, compute the equation of the radical of math.

  4. What is the dimension of the radical, of the quotient ?

  5. Write a function radNormal that normalize an element of math modulo its radical.

Suppose that math is an algebra with a basis math. In MuPAD, math is a certain domain Alg. The basis math of math is indexed by the element of the domain Alg::basisIndices. Like all combinatorial domain this domain may have a list method which can be called by Alg::basisIndices::list.

  1. Write a function GetBasis to compute a basis of an algebra or more generally of a free module.

  2. Write a function Generic Element to compute a generic element;

  3. Write a function Radical to compute the radical of an algebra.

1.4.1. Correction

Perm := n -> combinat::subClass(combinat::permutations, Parameters=n):


domain SGAx(n: Type::NonNegInt)

    category Cat::AlgebraWithBasis(Dom::ExpressionField());

    inherits Dom::FreeModule(Dom::ExpressionField(), Perm(n));

    axiom Ax::normalRep;


    one := dom::term( [ $ 1..n ] );


    mult2Basis :=

    proc(p1: dom::basisIndices, p2: dom::basisIndices)


dom::term( dom::basisIndices::_mult(p1,p2) );





domain Hecke0(n: Type::NonNegInt)

    category Cat::AlgebraWithBasis(Dom::ExpressionField());

    inherits Dom::FreeModule(Dom::ExpressionField(), Perm(n));

    axiom Ax::normalRep;


    basisName := hold(pi);


    one := dom::term( [ $ 1..n ] );


    mult2Basis :=

    proc(p1: dom::basisIndices, p2: dom::basisIndices)

local tmp;


for t in combinat::permutations::reducedWord(p2) do

    if p1[t] < p1[t+1] then

tmp    := p1[t];

p1[t]  := p1[t+1];

p1[t+1]:= tmp;







H3 := Hecke0(3):


Pi1 := H3([2,1,3]);

Pi2 := H3([1,3,2]);

Pi1*Pi2*Pi1 - Pi2*Pi1*Pi2;


_plus(combinat::permutations::sign(p)*H3(p) $ p in Perm3::list()) ;

x:=_plus(combinat::permutations::sign(p)*H3(p) $ p in Perm3::list()) ;


x^2-x ;


y := _plus( a[op(p)]*H3(p) $ p in Perm3::list() ) ;

makeCoeff := p -> hold(a)[op(p)];

y:=H3::genericElement(makeCoeff) ;

y^2-y ;

//res := solve([coeff(y^2-y)], H3::genericCoefficients(makeCoeff)):

//nops(res) ;