[Previous] [Next] [Contents]

Exercices

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

>> package("Combinat"):

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

>> export(combinat):

Using existing combinatorial classes

Exercise:

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

Exercise: Draw all the Dyck paths of length 6. Hint: use map, combinat::dyckWords::list, and combinat::dyckWords::printPretty.

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 combinat::integerVectors.

Exercise: Draw all the tableaux of size 4. Hint: use combinat::partitions::list, combinat::tableaux::list and combinat::tableaux::printPretty.

Exercise: Count the number of partitions of 1000 with parts bounded below by 10. Hint: first try out how far you can go with combinat::partitions. Then, switch to combinat::decomposableObject and use Multiset, Sequence, and MinLength. Hint: check the examples of use of combinat::decomposableObject in the guided tour.

Using generators

Exercise: Try and analyze the following piece of code:

>> (g := combinat::partitions::generator(4); 
   while (p := g()) <> FAIL do
     print(p, combinat::partitions::printPretty(p))
   end_while)
     

Exercise:

  1. Analyze the following piece of code:
    >> makeGen :=
       proc()
           option escape;
           local i;
       begin
           i := 0;
           proc() begin i:=i+1; end;
       end:
       g:=makeGen():
       g(), g(), g(), g(), g()
         
  2. Modify this piece of code to build a generator for the cube powers of integers: 1, 8, 27, ...
  3. Write a function that takes a power p and returns a generator for all the p-th powers of integers.
  4. Reimplement those generators using the functions combinat::generators::fromNext and combinat::generators::map.

Exercise:

  1. Build a generator for all the standard tableaux of size 4. Hint: use combinat::generators::pipe.
  2. Build a generator for all the standard tableaux of any size.
  3. 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.

Exercise:

  1. Compute the average number of inversions among all the permutations of n=7 that avoid the pattern [1,4,3,2]. Hint: use combinat::permutations::inversionsNumber and combinat::permutations::hasPattern, and try out the following examples:
    >> select([1,2,3,4,5,6,7,8], not isprime);
           
    Evaluate the complexity in time and memory of this computation.
  2. Compute the same thing with a memory complexity of O(n). Hint: use generators, combinat::generators::select, and try out this example:
    >> 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
           

Implementing new algebras

Exercise:

  1. 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])
           
  2. Implement a function coconcat(u) that returns the list of all the couples of words v and w such that u=v.w:
    >> coconcat([1, 2, 3])
         
          [[[], [1, 2, 3]], [[1], [2, 3]], [[1, 2], [3]], [[1, 2, 3], []]
          
             ]
            
  3. Make the shuffle algebra into a Hopf algebra (category Cat::HopfAlgebraWithBasis) by inserting the following method:
    >> coproductBasis :=
       proc(u: words) : ShuffleAlgebra
           local v;
       begin
           _plus(dom::tensorAlgebra(v) $ v in coconcat(u))
       end_proc:
           
    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 S⊗S via the product. You may wish to issue:
    >> export(operators, coproduct, mu):
           
  4. Use this to check, on some examples, that this is indeed a Hopf algebra; that is that the product and coproduct are compatible.
  5. Add the missing implementations for the counit and the antipod of the Hopf algebra.
  6. 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.

The degenerate Hecke Algebra

The Iwahori-Hecke algebra Hn(q) is the C-algebra generated by elements Ti for i<n with the relations: 2 T_i^2=(q-1)T_i+q for 1≤i ≤n-1,
T_iT_j=T_jT_i for |i-j|>1,
T_iT_i+1T_i =T_i+1T_iT_i+1T for 1≤i ≤n-2, The 0-Hecke algebra is obtained by setting q=0 in these relations. Then, the first relation becomes Ti2=-Ti. Let πi := 1+Ti.

  1. Use combinat::subClass to define the combinatorial class of the permutations of n.
  2. Define a parameterized domain HeckePi(n) for the Hecke algebra in the basis σ)σ∈ Sn with coefficient the rational (Dom::rational).
  3. Define the elementary generator πi. Check some braid relations.
  4. Define a parameterized domain HeckeT(n) for the Hecke algebra in the basis (Tσ)σ∈ Sn with coefficient the rational (Dom::rational).
  5. Check for small n that sum and alternating sum of the Tσ are two idempotents.
  6. Define the change of basis between the two versions. This can be done by hands or using the Bruhat order (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 Hn(0). We use a characterization from Dickson. theoremTheorem[section] Theorem: Let A be a sub algebra of Mn(F) for a field F of zero characteristic. Then x∈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. For finite dimensional algebra A, we realize A as a matrix algebra by considering any faithful representation, for example the regular one.
  1. Let g := ∑σ∈ Sn aσ Πσ be the generic element of Hn(0). Compute g and the generating family (gΠμ)μ∈ Sn for the ideal.
  2. Write a function trace that compute the trace of the endomorphism x∈Hn(0) →x e where e∈Hn(0).
  3. Using Dickson criterion, compute the equation of the radical of Hn(0).
  4. What is the dimension of the radical, of the quotient ?
  5. Write a function radNormal that normalize an element of Hn(0) modulo its radical.
Suppose that A is an algebra with a basis B. In MuPAD, A is a certain domain Alg. The basis B of A 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.

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package