[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